algo-aha

实际是两指针法，要利用某种单调性。[lo,hi]是子段，每次hi移动一步，lo移动0步或多步。

• 常见伸缩滑动窗口，写法关键是使窗口保持有效条件。
• 求最长窗口长，可用不收缩滑动窗口：窗口无效时lo只移动一步（不用while而用if），窗口大小保持不变、整体右移一步。窗口内暂时打破了有效条件，但循环结束时能确定找到最长窗口长N-lo。
• 用滑动数组解子段和问题，需要数组全部非负数，即presum[]数组单调递增

包含某些字符的最小窗口

• https://leetcode.com/problems/minimum-window-substring/
• https://leetcode.com/problems/find-all-anagrams-in-a-string/
• https://leetcode.com/problems/replace-the-substring-for-balanced-string/
• https://leetcode.com/problems/permutation-in-string/
• https://leetcode.com/problems/substring-with-concatenation-of-all-words/

string minWindow(string s, string t) {
    if (s.empty() || s.size() < t.size()) return "";
    unordered_map<char, int> cnt;
    for (char c : t) cnt[c]++;
    int distinct = cnt.size();
    
    int minWidth = INT_MAX, ansLo;
    for (int hi = 0, lo = 0; hi < s.size(); hi++) {
        if (--cnt[s[hi]] == 0) distinct--;
        while (distinct == 0) { // 有效窗口
            if (hi - lo + 1 < minWidth) {
                minWidth = hi - lo + 1;
                ansLo = lo;
            }
            if (cnt[s[lo]]++ == 0) distinct++;
            lo++;
        }
    }
    return minWidth != INT_MAX ? s.substr(ansLo, minWidth) : "";
}

相关：含某些字符的最小窗口用滑动窗口，含子序列的最小窗口用动态规划。

可替换<=k个字符，连续单字符的最长子段长

• https://leetcode.com/problems/longest-repeating-character-replacement

int characterReplacement(string s, int k) {
    const int N = s.size();
    unordered_map<char, int> count;
    int maxCnt = 0, lo = 0;
    for (int hi = 0; hi < N; hi++) {
        // 每一步都尝试将窗口长度推到极限 maxCnt+k
        // 不收缩滑动窗口，窗口不符合条件时整体右移一步
        maxCnt = max(maxCnt, ++count[s[hi]]);
        if (hi - lo + 1 > maxCnt + k) {
            count[s[lo]]--;
            lo++;
        }
    }
    return N - lo;
}

含全部三种字符的子段数

• https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/

int numberOfSubstrings(string s) {
    const int N = s.size();
    unordered_map<int, int> cnt; // char=>count
    int ans = 0;
    for (int hi = 0, lo = 0; hi < N; hi++) {
        cnt[s[hi]]++;
        while (cnt['a'] && cnt['b'] && cnt['c']) {
            cnt[s[lo++]]--;
        }
        // 现在[lo..hi]里字符不够，但前面的lo=[0..lo-1]都够
        ans += lo; // 关键是这里，在不合法状态计算合法状态数
    }
    return ans;
}

满意的顾客数

• https://leetcode.com/problems/grumpy-bookstore-owner/

int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
    // 滑动窗口记录X分钟内的不满意者xUnsatis
    const int N = customers.size();
    int satis = 0, xUnsatis = 0, maxUnsatis = 0;
    for (int hi = 0; hi < N; hi++) {
        if (!grumpy[hi]) satis += customers[hi];
        if (grumpy[hi]) xUnsatis += customers[hi];
        if (hi >= X && grumpy[hi-X]) xUnsatis -= customers[hi-X];
        maxUnsatis = max(maxUnsatis, xUnsatis);
    }
    return satis + maxUnsatis;
}