# [LeetCode] 395. Longest Substring with At Least K Repeating Characters 至少有K个重复字符的最长子字符串

2021年09月15日 阅读数：1

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.html

Example 1:java

```Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.
```

Example 2:python

```Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.```

Java:app

```public int longestSubstring(String s, int k) {
HashMap<Character, Integer> counter = new HashMap<Character, Integer>();

for(int i=0; i<s.length(); i++){

char c = s.charAt(i);
if(counter.containsKey(c)){
counter.put(c, counter.get(c)+1);
}else{
counter.put(c, 1);
}

}

HashSet<Character> splitSet = new HashSet<Character>();
for(char c: counter.keySet()){
if(counter.get(c)<k){
}
}

if(splitSet.isEmpty()){
return s.length();
}

int max = 0;
int i=0, j=0;
while(j<s.length()){
char c = s.charAt(j);
if(splitSet.contains(c)){
if(j!=i){
max = Math.max(max, longestSubstring(s.substring(i, j), k));
}
i=j+1;
}
j++;
}

if(i!=j)
max = Math.max(max, longestSubstring(s.substring(i, j), k));

return max;
}　　```

Python:less

```class Solution(object):
def longestSubstring(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
def longestSubstringHelper(s, k, start, end):
count = [0] * 26
for i in xrange(start, end):
count[ord(s[i]) - ord('a')] += 1
max_len = 0
i = start
while i < end:
while i < end and count[ord(s[i]) - ord('a')] < k:
i += 1
j = i
while j < end and count[ord(s[j]) - ord('a')] >= k:
j += 1

if i == start and j == end:
return end - start

max_len = max(max_len, longestSubstringHelper(s, k, i, j))
i = j
return max_len

return longestSubstringHelper(s, k, 0, len(s))
```

C++:post

```class Solution {
public:
int longestSubstring(string s, int k) {
int res = 0, i = 0, n = s.size();
while (i + k <= n) {
int m[26] = {0}, mask = 0, max_idx = i;
for (int j = i; j < n; ++j) {
int t = s[j] - 'a';
++m[t];
if (m[t] < k) mask |= (1 << t);
else mask &= (~(1 << t));
res = max(res, j - i + 1);
max_idx = j;
}
}
i = max_idx + 1;
}
return res;
}
};
```

C++:url

```class Solution {
public:
int longestSubstring(string s, int k) {
int n = s.size(), max_idx = 0, res = 0;
int m[128] = {0};
bool ok = true;
for (char c : s) ++m[c];
for (int i = 0; i < n; ++i) {
if (m[s[i]] < k) {
res = max(res, longestSubstring(s.substr(max_idx, i - max_idx), k));
ok = false;
max_idx = i + 1;
}
}
return ok ? n : max(res, longestSubstring(s.substr(max_idx, n - max_idx), k));
}
};
```