题解 | #最小覆盖子串#

class Solution {
public:
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    
    string minWindow(string S, string T) {
        int left = 0, right = 0;
        //表示窗口左右位置的指针
        int start = 0, minLen = INT_MAX;
        //start 表示最后结果字符串开始位置，minlen表示最后字符串长度，二者可以表示一个字符串
        unordered_map<char, int> need;
        //need的存放字符串T的所有字符统计
        unordered_map<char, int> window;
        //window 存放现有的窗口中出现在need中的字符统计

        for (auto i:T)
            need[i]++;
        int match = 0;
        //window与need的匹配度

        while (right < S.length()) {
            char c1 = S[right];
            if (need.count(c1)) { // 看need字典中是否存在c1
                window[c1]++;
                if (window[c1] == need[c1]) // 如果窗口中出现的c1次数等于T字符串中的次数
                    match++;
            }
            right++;
            while (match == need.size()) { // 此处是need.size()不是T.size()，考虑到T中可能存在重复字符的因素
                //当匹配度等于need.size(),说明这段区间可以作为候选结果，更新ret
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }
                char c2 = S[left];
                if (need.count(c2)) {
                    window[c2]--;
                    if (window[c2] < need[c2]) 
                        match--;
                }
                left++;
            }
        }
        return minLen == INT_MAX ? "" : S.substr(start, minLen);
    }

};