395. Longest Substring with At Least K Repeating Characters

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

找由[a-z]组成的字符串S中每个字符都至少出现K次的最长子串。substring+longest => 动态窗口。但这道题并不像一般的动态窗口题只需直接扫描一次，因为以S[r]为底时，以满足问题条件使得l前移的停止条件却不满足一般滑动窗口适用的条件: l前移过的都无需再考虑。比如S = abba, K = 2, 到第二个b时l移到第一个b以拼出满足问题条件的字串，此时l略去过的第一个a明显不该丢掉。 这时要利用到问题的另一个遍历角度: 每个符合条件的子串可能有多少种不同的字符。S由[a-z]构成，也就是最多有26个不同字符。因此问题转化成给定cnt，找S中每个字符都至少出现K次且字符种类不超过cnt的最长子串，也就是Longest Substring with At Most K Distinct Characters。cnt条件才是滑动窗口对l操作真正的条件，遍历所有不超过cnt的子串，统计满足频率都达到K的作为最后的结果候选。

/*
 * @lc app=leetcode id=395 lang=cpp
 *
 * [395] Longest Substring with At Least K Repeating Characters
 */

// @lc code=start
class Solution {
public:
    int longestSubstring(string s, int k) {
        int l = 0, r = 0, sat = 0, res = 0;
        unordered_map<char, int> freqs;
        for (int cnt = 1; cnt <= 26; ++cnt) {
            freqs.clear();
            l = r = sat = 0;
            while (r < s.length()) {
                const auto key = s[r];
                ++freqs[key];
                if (freqs[key] == k) ++sat;
                while (freqs.size() > cnt) {
                    const auto lk = s[l];
                    if (freqs[lk] == k) --sat;
                    --freqs[lk];
                    ++l;
                    if (freqs[lk] == 0) freqs.erase(lk);
                }
                if (sat == cnt) res = max(res, r - l + 1);
                ++r;
            }
        }
        return res;
    }
};
// @lc code=end