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)

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

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;
}