NC28.最小覆盖子串

class Solution {
public:
    string minWindow(string S, string T) {
        unordered_map<char, int> WinMap;
        unordered_map<char, int> TMap;
        for (auto& i : T) ++TMap[i];

        int l = 0, r = -1;
        int cnt = 0;
        string minWin, win;

        while (r < (int)S.length()) {
            [&](char c) {
                if (TMap.count(c)) {
                    ++WinMap[c];
                    if (WinMap[c] == TMap[c]) ++cnt;
                }
            }(S[++r]);    // 增大窗口
            while (cnt == (int)TMap.size()) {
                win = S.substr(l, r - l + 1);    // 获取窗口
                minWin = !minWin.empty() && minWin.length() < win.length() ? minWin : win;    // 获取值
                [&](char c) {
                    if (TMap.count(c)) {
                        if (WinMap[c] == TMap[c]) --cnt;
                        --WinMap[c];
                    }
                }(S[l++]);    // 缩小窗口
            }
        };
        return minWin;
    }
};

解题思路：

难点1：这题第一次做确实很难，参考了答案；

难点2：滑动窗口算法的固定形态，不熟悉当场思考比较难；

难点3：增大、缩小窗口的两个lambda函数抽象至关重要；在增大和缩小窗口的时候分别同步窗口的相关状态；

            [&](char c) {
                if (TMap.count(c)) {
                    ++WinMap[c];
                    if (WinMap[c] == TMap[c]) ++cnt;
                }
            }(S[++r]);    // 增大窗口

                [&](char c) {
                    if (TMap.count(c)) {
                        if (WinMap[c] == TMap[c]) --cnt;
                        --WinMap[c];
                    }
                }(S[l++]);    // 缩小窗口

难点4：如何判断窗口中含有几个T中的字符，使用了两个map和一个变量cnt解决，非常巧妙！

难点5：个人认为r从-1开始，逻辑上更加完备；

知识点

知识点1：滑动窗口算法的固定形态：

T swiftWindow(string s, T args...) {
    T rst;
    int l = 0, r = -1;
    while (r < (int)s.length()) {
        [&](char c) {
            // ...
            // 窗口状态更新，添加增大量
        }(s[++r]);                          // 增大窗口
        bool cond = [] { /*...*/ };    // 达到缩小窗口的条件
        while (cond) {
            [&](char c) {
                // ...
                // 窗口状态更新，减少缩小量
            }(s[l++]);                      // 缩小窗口
        }
    }
    return rst;
}