0395. Longest Substring with At Least K Repeating Characters.md

0395. Longest Substring with At Least K Repeating Characters, medium, , freq: 21%, acceptance: 39.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.

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.

// 4ms, 83%
class Solution {
public:
    int longestSubstring(const string& s, int k) {
        int res = 0;
        vector<int> buf(26, 0);
        for (int i = 0; i < s.size(); i++) buf[s[i]-'a']++;
        
        int i = 0;
        while (i < s.size() && buf[s[i]-'a'] >= k) i++;
        if (i == s.size()) return i;
        
        int left = longestSubstring(s.substr(0, i), k);
        while (i < s.size() && buf[s[i]-'a'] < k) i++;
        if (i == s.size()) return left;
        
        int right = longestSubstring(s.substr(i), k);
        return max(left, right);
    }
};

// 188ms, 12%
// if found one substring, the next one will not overlap with the previous one
class Solution {
public:
    int longestSubstring(string s, int k) {
        int res = 0;
        for (int i = 0; i + k <= s.size(); ) {
            int mask = 0;
            vector<int> buf(26, 0);
            int lastj = i+1;
            for (int j = i; j < s.size(); j++) {
                char c = s[j] - 'a';
                buf[c]++;
                if (buf[c] < k) mask |= (1 << c);
                else mask &= ~(1 << c);
                
                if (mask == 0) {
                    res = max(res, j - i + 1);
                    lastj = j + 1;
                }
            }
            i = lastj;
        }
        return res;
    }
};