题目描述

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

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

说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

解题思路：

使用左右指针滑动窗口的思想解决。
r指针用于延伸现有窗口，l指针用于收缩窗口。当窗口满足条件时，看能否收缩到最小窗口。
条件判断：用一个hash表表示t中所有字符以及个数。用另一个hash表表示当前窗口的字符和个数。

    unordered_map<char, int> ori, cnt;
    bool check(){
        for(const auto& p: ori){
            if(cnt.find(p.first)==cnt.end() || cnt[p.first]<p.second)
                return false;
        }
        return true;
    }

    string minWindow(string s, string t){
        for(auto c:t){
            ori[c]++;
        }

        int len = INT32_MAX, anL = -1;
        int l=0, r=-1;
        while(r<s.size()){
            if(ori.find(s[++r])!=ori.end())
                ++cnt[s[r]];

            while(l<=r && check()){
                if(r-l+1<len){
                    len = r-l+1;
                    anL = l;
                }

                if(ori.find(s[l])!=ori.end())
                    --cnt[s[l]];
                l++;
            }
        }

        return anL==-1 ? string("") : s.substr(l, len);
    }