Niuke network: minimum coverage substring

This is the idea ：

We maintain a speed pointer slow and fast, And a hash table

The hash table is used to record in S[slow,fast] Whether or not there is... In this string interval T In the character , If so, then >=0, At the beginning, it is initialized to -1. After that we will only update and T String related elements , It can be used unordered_map A function of count, If the element we are looking for is in it, we return 1, If not, return 0

Then let's maintain this interval , We make use of fast To traverse the entire string S：

1. Take out S[fast], If this element is T The elements in , Then the hash table record is incremented by one

2. If it is in the current maintenance interval [slow,fast] In the T All characters in , The length of the shortest string is updated , And update the interval to be returned [left, right] The value of is [slow, fast]

After the update , We try to reduce the size of the interval , About to take out the left element , take slow Add 1, Update hash table , Continue with the first judgment in step 2

The code is as follows ：

class Solution {
public:
    /**
     * 
     * @param S string character string  
     * @param T string character string  
     * @return string character string 
     */
    bool check(unordered_map<char, int> &hash){
        for(auto iter=hash.begin();iter!=hash.end();++iter){
            if(iter->second<0){
                return false;
            }
        }
        return true;
    }
    string minWindow(string S, string T) {
        int cnt=S.length()+1;
        unordered_map<char, int> hash;
        for(int i=0;i<T.length();++i){
            hash[T[i]] -= 1;
        }
        int slow=0,fast=0;
        int left=-1,right=-1;
        for(;fast<S.length();++fast){
            char c=S[fast];
            if(hash.count(c)){
                hash[c]++;
            }
            while(check(hash)){
                // If the length is less than the minimum value of the current record 
                // Update interval value 
                if(cnt > fast-slow+1){
                    cnt=fast-slow+1;
                    left=slow;
                    right=fast;
                }
                // As long as it is satisfied to appear t Conditions for all characters of 
                // Just try to narrow the left range 
                char c=S[slow];
                if(hash.count(c)){
                    hash[c]--;
                }
                slow++;
            }
        }
        if(left==-1){
            return "";
        }
        return string(S.begin()+left, S.begin()+right+1);
    }
};