滑动窗口 $O(n)$

• 两个哈希表：need存T中所有字母的出现次数，window存窗口中T中字母出现的次数
  valid表示窗口中满足need的条件的字符个数：若valid==need.size(),说明窗口已经完全覆盖了串T
  可以收缩窗口，并更新最小长度子串的起始位置和长度

• 注：扩张窗口和收缩窗口更新的数据信息是对称的
  写代码需考虑4个问题:
  1.扩张窗口时需要更新哪些数据
  2.收缩窗口的条件是什么
  3.收缩窗口时需要更新哪些数据(与扩张时对称)
  4.在哪个位置更新结果(本题在每次收缩窗口前更新最小子串信息)

class Solution {
public:
    string minWindow(string s, string t) {
        if(s.size()<t.size()) return "";
        unordered_map<char,int> need,window;
        for(const char c:t)                 //记录模式串频次情况
            need[c]++;

        int left=0,right=0;
        int valid=0,start=0,len=INT_MAX;    //start、len记录最小覆盖子串的起点和长度
                                            //valid表示T中多少种字符已经全部在窗口内
        while(right<s.size())
        {
            char c=s[right++];              //扩张窗口
            if(need.count(c))               //更新数据
            {
                window[c]++;
                if(window[c]==need[c])
                    valid++;
            }

            while(valid==need.size())       //收缩条件(只要当前窗口内仍包含T所有字符则收缩)
            {
                if(right-left<len)          //收缩前更新最小覆盖子串信息
                {
                    start=left;
                    len=right-left;
                }
                char c=s[left++];           //收缩窗口
                if(need.count(c))           //更新数据           
                {
                    if(window[c]==need[c])           
                        valid--;
                    window[c]--;
                }
            }
        }
        return len==INT_MAX ? "" :s.substr(start,len);
    }
};