题解 | #最小覆盖子串#

#include <string>
#include <unordered_map>
class Solution {
public:
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // write code here
        int m = S.size();
        int n = T.size();
        string res = S + "max";
        unordered_map<char, int> smap,tmap;
        for(int i = 0;i<n;++i)
            tmap[T[i]]++;
        int left = 0;
        int count = 0;
        for(int right = 0;right < m;++right)
        {
            if(tmap[S[right]] > smap[S[right]])
                count++;
            smap[S[right]]++;
            while(left < right && smap[S[left]] > tmap[S[left]])
                smap[S[left++]]--;
            if(count == n)
            {
                if(right-left+1 < res.size())
                    res = S.substr(left,right-left+1);
            }
        }
        return res == S + "max"? "":res;
    }
};