题解 | 最小覆盖子串

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // write code here
        unordered_map<char,int>need;//记录T中每个字符需要的次数
        unordered_map<char,int>window;//记录当前窗口中每个字符出现的次数
        for(char c:T)
        {
            need[c]++;//记录每个字符出现的次数
        }
        int valid=0;//记录有多少种字符满足了需求
        int left=0;//左指针
        int right=0;//右指针
        int start=0;
        int len=10001;
        while(right<S.size())
        {
            char c=S[right];
            right++;
            
            if(need.count(c))//确定S当前字符是在T里面的
            {
                window[c]++;//当前窗口中字符c的出现次数+1
                //只有当字符出现次数与需要次数相等时，valid才会增加。有时会出现T中字符在当前窗口中出现了多次
                //但是valid不应该增加，这个时候在尝试增大left，缩小窗口时，越过当前字符，虽然window会减1
                //但是它不影响T中字符都出现在当前窗口的结果
                if(need[c]==window[c])
                {
                    valid++;
                }
            }

            while(valid==need.size())//当所有种字符都满足需求时，此时尝试减少长度
            {
                if(right-left<len)//先把当前满足的长度记录下来
                {
                    start=left;
                    len=right-left;
                }
                char d=S[left];
                left++;//尝试增大left，缩小整体字符串的长度
                if(need.count(d))//如果原来的left对应的字符是T中的字符，那么首先window中对应字符出现的次数要减1
                {
                    //此时如果字符d出现的次数与要求的次数相等，因为已经缩小，所以满足要求的有效字符数要减1
                    //因为要越过字符d，所以是先判断越过之前是正好与需要次数相等，如果相等，则Valid满足条件的字符数减1
                    if(window[d]==need[d])
                    {
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return len==10001?"":S.substr(start,len);
    }
};