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

```python
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),

```python
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)
```

**Code: C++ O(n^2) with mask**

```cpp
int longestSubstring(string s, int k) {
   int max_len = 0;
   for (int first = 0; first+k <= s.size();) {
       int count[26] = {0};
       int mask = 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));

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