题解 | #最小覆盖子串#

滑窗题
时间复杂度：
空间复杂度：

class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.length();
        unordered_map<char, int> ump, curUmp;
        int target = 0;
        for(char ch:t) ump[ch] ++, target ++;
        int ans = INT_MAX;
        int cnt = 0;
        int end = -1;
        string res;
        for(int i = 0; i < n; i ++){
            if(i > 0){
                if(ump.count(s[i - 1]) > 0 && curUmp[s[i - 1]] <= ump[s[i - 1]]) cnt --;
                curUmp[s[i - 1]] --;

            }
            while(end + 1 < n && cnt < target){
                end ++;
                curUmp[s[end]] ++;
                if(ump.count(s[end]) > 0 && curUmp[s[end]] <= ump[s[end]]) cnt ++;
            }
            if(cnt == target){
                if(ans > end - i + 1){
                    ans = end - i + 1;
                    res = s.substr(i, ans);
                }
            }
        }
        return res;
    }
};