LeetCode 76.最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
算法：双指针，哈希表(注意此题与最长连续不重复子序列以及最长上升子序列的区别)。

需要注意的是，我们在维护哈希表的时候，需要判断的是如果目标串的某个字符个数已经超过匹配串相应的字符个数

这里对应的下标应该是j不是i(具体见代码)。

class Solution {
public:
    string minWindow(string s, string t) {
        string res;
        unordered_map<char,int>T,S;
        for(auto x:t)T[x]++;
        int total=T.size(),st=0;
        for(int i=0,j=0;i<s.size();i++){
            S[s[i]]++;
            if(S[s[i]]==T[s[i]])st++;
            while(j<=i&&S[s[j]]>T[s[j]])S[s[j++]]--;
            if(st==total&&(res.empty()||i-j+1<res.size()))
                res=s.substr(j,i-j+1);
        }
        return res;
    }
};

LeetCode 76.最小覆盖子串

推荐阅读