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

// Sliding Window
int longestSubstring(string s, int k) { // time: O(n^2); space: O(1)
    int begin = 0, d = 0, n = s.length();
    while (begin + k <= n) {
        vector<int> count(26, 0);
        int mask = 0, maxLast = begin;
        for (int end = begin; end < n; ++end) {
            int idx = s[end] - 'a';
            ++count[idx];
            // bitmask toggling
            if (count[idx] < k) {
                mask |= (1 << idx);
            } else {
                mask &= (~(1 << idx));
            }
            if (mask == 0) {
                d = max(d, end - begin + 1);
                maxLast = end;
            }
        }
        begin = maxLast + 1;
    }
    return d;
}