题解 | #最小覆盖子串#

class Solution {
private:
    unordered_map<char, int> tar;
    unordered_map<char, int> src;
public:
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // write code here
        
        for(int i=0; i<T.length(); i++){
            tar[T[i]] += 1;
        }
        
        int left=0, right=0, res=INT_MAX;
        int res_start = -1;
        while(right < S.length()){
            while(right < S.length() && !check()){
                src[S[right]] += 1;
                right++;
            }
            
            while(check()){
                if(res > right-left){
                    res = right - left;
                    res_start = left;
                }
                src[S[left]] -= 1;
                if(src[S[left]] == 0){
                    src.erase(S[left]);
                }
                left++;
            }
            
        }
        if(res_start == -1){
            return "";
        }
        string out = S.substr(res_start, res);
        return out;
    }
    
    bool check(){
        for(auto it = tar.begin(); it != tar.end(); it++){
            if(src.find(it->first) == src.end()){
                return false;
            }
            else if(src[it->first] < it->second){
                return false;
            }
        }
        return true;
    }
    
};