题解 | #最小覆盖子串#

class Solution {
public:
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // write code here
        int n = S.size();
        int m = T.size();
      	// 特判，如果S比T短，不符合题意
        if( n < m)
            return "";
        int l = 0;				// 窗口左右边界
        int r = 0;
        int len = INT_MAX;		// 窗口长度
        int start = -1;			// 最小区间起始位置
      	// 记录T中元素出现情况，因为可能会出现一个元素出现多次的情况，故用map而不用set
        unordered_map<char, int> cache;
      	// 记录S中出现目标元素的情况
        unordered_map<char, int> window;
      	// 已完成覆盖的元素类别数
        int valid = 0;
        
        for(auto x : T)
            cache[x]++;
        
        //滑动
        while(r < n ){
            
            // 窗口扩展
            char cur_r = S[r++];
            if(cache.count(cur_r)){
                window[cur_r]++;
                if(window[cur_r] == cache[cur_r])
                    valid++;
            }
            
            //窗口收缩
            while(valid == cache.size()){
                if(len > r - l){
                    len = r - l;
                    start = l;
                }
                char cur_l = S[l++];
                if(cache.count(cur_l)){
                    if(window[cur_l] == cache[cur_l])
                        valid--;
                    window[cur_l]--;
                }
            }
            
        }
        return len == INT_MAX ? "" : S.substr(start,len);
        
    }
};