76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

> 思路
滑动窗口

> 代码

class Solution {
public:
    string minWindow(string s, string t) {
        int len1 = s.size();
        int len2 = t.size();
        if(len1 < len2) return "";
        unordered_map<char,int> mp_s;
        unordered_map<char,int> mp_t;
        for(const auto& c:t){
            mp_t[c]++;
        }
        int l = 0;
        int r = 0;
        int valid = 0;
        int start = 0;
        int len_r = INT_MAX;
        while(r < len1){
            // c是要移入窗口的字符
            char c = s[r];
            // 右移指针
            r++;
            // 进行窗口更新
            if(mp_t.count(c)){
                mp_s[c]++;
                if(mp_s[c] == mp_t[c]){
                    valid++;
                }
            }
            //判断左侧窗口需要收缩
            while(valid == mp_t.size()){
                // 在这里更新最小覆盖子串
                if(r - l < len_r){
                    start = l;
                    len_r = r - l;
                }
                // d是将移出窗口的字符
                char d = s[l];
                //窗口左移
                l++;
                // 进行窗口更新
                if(mp_t.count(d)){
                    if(mp_t[d] == mp_s[d]){
                        valid--;
                    }
                    mp_s[d]--;
                }
            }
        }
        return len_r == INT_MAX?"":s.substr(start,len_r);
    }
};