题解 | 最小覆盖子串

恶心，题目文字没说子串的数量也要算进去，虽然示例2里展示了重复字符数量的问题，但我没看示例2）

下面提供两个版本的

使用reducewindow1和satisfywindow1的是只要提取的子串的字符集合包含目标子串即可。

使用xxx2和yyy2的是提取的子串的每个字符的数量也要大于等于目标子串的对应字符数量。

#include <limits>
#include <unordered_map>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    static unordered_map<char, int> stat_target;
    static bool initialized;
    bool reducewindow1(unordered_map<char, int>& stats, string target) {
        for (auto ch : target)
            if (stats[ch] < 1) return false;
        return true;
    }
    bool reducewindow2(unordered_map<char, int>& stats, string target) {
        for (auto ch : target)
            if (stats[ch] < stat_target[ch]) return false;
        return true;
    }

    bool satisfywindow1(unordered_map<char, int>& stats, string target) {
        for (auto ch : target) if (stats[ch] < 1) return false;
        return true;
    }

    bool satsifywindow2(unordered_map<char, int>& stats, string target) {
        for (auto ch : target) if (stats[ch] < stat_target[ch]) return false;
        return true;
    }

    string minWindow(string S, string T) {
        if (S.size() < T.size()) return "";
        for (auto ch : T) stat_target[ch] = 0;
        for (auto ch : T) stat_target[ch] += 1;
        this->initialized = true;
        unordered_map<char, int> stats;
        for (auto ch : S) stats[ch] = 0;
        int l = 0, r = 0;
        int minstart = 0, minlen = numeric_limits<int>::max();
        while ( r < S.size()) {
            while (r < S.size() && !satsifywindow2(stats, T)) stats[S[r++]] += 1;
            while (reducewindow2(stats, T)) stats[S[l++]] -= 1;
            if (r - l + 1 < minlen) {
                minlen = r - l + 1;
                minstart = l - 1;
            }
        }
        if (minstart < 0) return "";
        return S.substr(minstart, minlen);
    }
};

unordered_map<char, int> Solution::stat_target{};
bool Solution::initialized = false;