## 395. Longest Substring with At Least K Repeating Characters

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 thanktimes.

Example 1:

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

Output:
3

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

Example 2:

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

Output:
5

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

Thoughts:

1. find the smallest count character c in the array, split the string s with the character c and resursively calling the all the substring, return the max value from them
2. or just find the first character that has count less than k and then do the split

Code: T: O(n), because there are at most 26 levels of recursions.

``````class Solution(object):
def longestSubstring(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
# base case
if len(s)<k: return 0
c = min(set(s), key = s.count) # get the char with lowest count in s
if s.count(c) >=k: return len(s)

return max(self.longestSubstring(t, k) for t in s.split(c))
``````

Code: T: O(n),

``````class Solution(object):
def longestSubstring(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
for c in set(s):
if s.count(c) < k:
return max(self.longestSubstring(t,k) for t in s.split(c))

# base case if is an empty set or s itslef is the longest answer
return len(s)
``````

``````int longestSubstring(string s, int k) {
int max_len = 0;
for (int first = 0; first+k <= s.size();) {
int count[26] = {0};
int max_last = first;
for (int last = first; last < s.size(); ++last) {
int i = s[last] - 'a';
count[i]++;
if (count[i]<k) mask |= (1 << i);
else   mask &= (~(1 << i));

max_len = max(max_len, last-first+1);
max_last = last;
}
}
first = max_last + 1;
}
return max_len;
}
``````