Leetcode 76. 最小覆盖子串

题目描述（难度hard）

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

• 如果 S 中不存这样的子串，则返回空字符串 ""。
• 如果 S 中存在这样的子串，我们保证它是唯一的答案。

解题思路

该题使用滑动窗口和两个哈希表，通过移动左右指针维护窗口，通过比较不断t和窗口字符出现频次找到包含 t 所有字符的最小子串

PS：为避免每次都要花费O(k)判断当前窗口字符出现包含t所有字符，使用变量correct记录有效字符出现次数，等于t.size后再判断是否是最小子串

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map <char,int> smap,tmap;
        string ans = s;
        for(auto c:t){
            tmap[c]++;
        }
        
        int left=0,correct=0;
        for(int right=0;right<s.length();right++){
            //smap维护当前窗口中字符出现数的哈希表
            smap[s[right]]++;
            //当前rigth对应s的字符是t中的字符并且还没有冗余，是有效添加
            if(tmap[s[right]] >= smap[s[right]]){//>=是因为先做的smap[s[right]]++;
                correct++;
            }
            //如果left对应的字符冗余，窗口就右移
            while(left < right && smap[s[left]] > tmap[s[left]]){
                --smap[s[left++]];
                //冗余——1.字符不在t中，不需要改动correct
                //2.字符在t中但过多了，直接去掉不需要改动correct
            }
            //如果窗口内的字符已经满足t串所有字符
            if(correct == t.size()){
                if(right-left+1 < ans.size()){
                    ans = s.substr(left,right-left+1);
                }
            }
        }
        if(correct < t.size())ans = "";
        return ans;
    }
};