Algorithm
Problem Name: 395. Longest Substring with At Least K Repeating Characters
Problem Link: https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.
Example 1:
Input: s = "aaabb", k = 3 Output: 3 Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
Input: s = "ababbc", k = 2 Output: 5 Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
Constraints:
1 <= s.length <= 104sconsists of only lowercase English letters.1 <= k <= 105
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const longestSubstring = function (s, k) {
if (s == null || s.length === 0) return 0
const chars = new Array(26).fill(0)
const aCode = 'a'.charCodeAt(0)
for (let i = 0; i < s.length; i++) chars[s.charCodeAt(i) - aCode] += 1
let flag = true
for (let i = 0; i < chars.length; i++) {
if (chars[i] < k && chars[i] > 0) flag = false
}
if (flag === true) {
return s.length
}
let result = 0
let start = 0
let cur = 0
while (cur < s.length) {
if (chars[s.charCodeAt(cur) - aCode] < k) {
result = Math.max(result, longestSubstring(s.slice(start, cur), k))
start = cur + 1
}
cur++
}
result = Math.max(result, longestSubstring(s.slice(start), k))
return result
}
Input
s = "aaabb", k = 3
Output
3
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def longestSubstring(self, s, k):
br = [-1] + [i for i, c in enumerate(s) if s.count(c) < k] + [len(s)]
return len(s) if len(br) == 2 else max(self.longestSubstring(s[br[i - 1] + 1:br[i]], k) for i in range(1, len(br)))
Input
s = "ababbc", k = 2
Output
5