395. 至少有 K 個重複字元的最長字串

推薦事前閱讀：滑動窗口

思路

如果單純用窗口，窗口不是越小越好，也不是越大越好，
一個s[i]~s[j]的子字串滿足條件，不代表更長的就一定滿足，
也就是不滿足單調性，窗口的大小跟限制沒有相關。
為了讓窗口跟限制具有相關，我們將原本的問題拆解成 26 個小問題。

• 子字串有且僅有一種字元，出現 $\geq{k}$ 次，最長多長？
• 子字串有且僅有二種字元，出現 $\geq{k}$ 次，最長多長？
• 子字串有且僅有三種字元，出現 $\geq{k}$ 次，最長多長？
• $\dots$

在上面算出的 26 個答案當中選一個最大的作為正式答案就好。

• 當 j 向右移動時，unique_cnt 只會增加或不變。
• 當 i 向右移動時，unique_cnt 只會減少或不變。

如果沒有額外的字元數量限制，就不知道當前窗口是應該繼續往右伸，還是縮減左邊界，
一旦加入了 require，左邊界就必須在 unique_cnt 太多的時候縮減。

在計算子問題的時候，使用 unique_cnt 紀錄出現了幾種字元，satisfy 紀錄有多少字元出現次數有 $\geq{k}$ 。

程式碼

滑動窗口

class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.length();
        int res = 0;
        // 每次要求子字串必須有 require 種字元，出現次數都 >= k 的最長子字串
        for(int require = 1; require <= 26; require++) {
            int cnt[128]{};
            int unique_cnt = 0, satisfy = 0;
            for(int i = 0, j = 0; j < n; j++) {
                cnt[s[j]]++;
                if(cnt[s[j]] == 1) unique_cnt++; // 新的字元被加入
                if(cnt[s[j]] == k) satisfy++;  // 增加之後達到了要求

                while(unique_cnt > require) { // 當前的字元太多，不得已需要縮減左邊界
                    if(cnt[s[i]] == 1) unique_cnt--;
                    if(cnt[s[i]] == k) satisfy--; // 減少了之後變得不符合要求
                    cnt[s[i++]]--;
                }
                
                // 此時 unique_cnt <= require, 而因為 satisfy 比 unique_cnt 限制更多，
                // 當 satisfy == require 時，unique_cnt == require。
                if(satisfy == require) {
                    res = max(res, j - i + 1);
                }
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$