题解 | #最小覆盖子串#

滑动窗口，双指针

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    string minWindow(string s, string T) {
        // write code here
        int n = s.size(), m = T.size();
        unordered_map<char, int> mp;
        for (char f : T) mp[f]++;
        unordered_map<char, int> cnt;
        int i = 0, j = 0;
        int res = INT_MAX;
        int left = -1;
        int state = 0;
        while (i < n) {
            if (mp.count(s[i])) {
                cnt[s[i]]++;
                if (cnt[s[i]] == mp[s[i]])
                    state++;
            }
            while (state == mp.size() && j <= i) {
                if (res > i - j + 1) {
                    left = j;
                    res = i - j + 1;
                }
                if (cnt.count(s[j])) {
                    if (cnt[s[j]] == mp[s[j]])
                        state--;
                    cnt[s[j]]--;
                }
                j++;
            }
            i++;
        }
        if (left == -1) return "";
        return s.substr(left, res);
    }
};



#ifdef debug

int main() {
    cout << " * [421] " << endl;
    Solution k;
    cout << "result:  " << k.minWindow("XDOYEZODEYXNZ", "XYZ") << endl;
    return 0;
}

#endif