Description
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.
if no such substring exists, return 0.
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 <= 104s consists of only lowercase English letters.1 <= k <= 105
Solutions
Solution 1
PythonJavaC++Go
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
def dfs(l, r):
cnt = Counter(s[l : r + 1])
split = next((c for c, v in cnt.items() if v < k), '')
if not split:
return r - l + 1
i = l
ans = 0
while i <= r:
while i <= r and s[i] == split:
i += 1
if i >= r:
break
j = i
while j <= r and s[j] != split:
j += 1
t = dfs(i, j - 1)
ans = max(ans, t)
i = j
return ans
return dfs(0, len(s) - 1)(code-box)
class Solution {
private String s;
private int k;
public int longestSubstring(String s, int k) {
this.s = s;
this.k = k;
return dfs(0, s.length() - 1);
}
private int dfs(int l, int r) {
int[] cnt = new int[26];
for (int i = l; i <= r; ++i) {
++cnt[s.charAt(i) - 'a'];
}
char split = 0;
for (int i = 0; i < 26; ++i) {
if (cnt[i] > 0 && cnt[i] < k) {
split = (char) (i + 'a');
break;
}
}
if (split == 0) {
return r - l + 1;
}
int i = l;
int ans = 0;
while (i <= r) {
while (i <= r && s.charAt(i) == split) {
++i;
}
if (i > r) {
break;
}
int j = i;
while (j <= r && s.charAt(j) != split) {
++j;
}
int t = dfs(i, j - 1);
ans = Math.max(ans, t);
i = j;
}
return ans;
}
}(code-box)
class Solution {
public:
int longestSubstring(string s, int k) {
function<int(int, int)> dfs = [&](int l, int r) -> int {
int cnt[26] = {0};
for (int i = l; i <= r; ++i) {
cnt[s[i] - 'a']++;
}
char split = 0;
for (int i = 0; i < 26; ++i) {
if (cnt[i] > 0 && cnt[i] < k) {
split = 'a' + i;
break;
}
}
if (split == 0) {
return r - l + 1;
}
int i = l;
int ans = 0;
while (i <= r) {
while (i <= r && s[i] == split) {
++i;
}
if (i >= r) {
break;
}
int j = i;
while (j <= r && s[j] != split) {
++j;
}
int t = dfs(i, j - 1);
ans = max(ans, t);
i = j;
}
return ans;
};
return dfs(0, s.size() - 1);
}
};(code-box)
func longestSubstring(s string, k int) int {
var dfs func(l, r int) int
dfs = func(l, r int) int {
cnt := [26]int{}
for i := l; i <= r; i++ {
cnt[s[i]-'a']++
}
var split byte
for i, v := range cnt {
if v > 0 && v < k {
split = byte(i + 'a')
break
}
}
if split == 0 {
return r - l + 1
}
i := l
ans := 0
for i <= r {
for i <= r && s[i] == split {
i++
}
if i > r {
break
}
j := i
for j <= r && s[j] != split {
j++
}
t := dfs(i, j-1)
ans = max(ans, t)
i = j
}
return ans
}
return dfs(0, len(s)-1)
}(code-box)
