题解 | #最小覆盖子串#

#include <climits>
#include <unordered_map>
class Solution {
  public:
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // 可变滑动窗口
        unordered_map<char, int> window, need;
        // 目标
        for (char& c : T) {
            ++need[c];
        }
        // start 和 len 记录答案
        int start = 0, len = INT_MAX;
        int left = 0, right = 0;
        // 记录有效字符数
        int valid = 0;
        while (right < S.length()) {
            char cur = S[right];
            ++right;
            // need不含有的字符，我们可以忽略
            // 如果need含有该字符，那我们需要更新window和valid
            if (need.count(cur)) {
                ++window[cur];
                if (window[cur] == need[cur])  ++valid;
            }
            // 在满足valid的条件下，循环判断最小的覆盖子串
            while (valid == need.size()) {
                if (right - left < len) {
                    len = right - left;
                    start = left;
                }
                char p = S[left];
                ++left;
                // 不管是right加入还是left删除
                // 同样的，只有need含有该字符时，我们去更新window窗口
                if (need.count(p)) {
                    // 删除前判断
                    if (window[p] == need[p]) --valid;
                    --window[p];
                }
            }
        }
        return len == INT_MAX ? "" : S.substr(start, len);
    }
};