题解 | #最小覆盖子串#

class Solution {
  public:
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // write code here

        //要匹配的字符， 和要匹配的个数
        map<char, int> Tmap;
        //字串的开始索引
        int bgIdx = 0;
        //最小窗口
        int winSize = INT_MAX;

        //记录要匹配的每一个元素的个数
        for (auto c : T) {
            Tmap[c]++;
        }


        //记录要匹配字符的个数
        int elemCnt = T.size();
        int l = 0;

        for (int r = 0; r < S.size(); ++r) {
            //如果属于要匹配的字符
            if (Tmap.find(S[r]) != Tmap.end()) {
                
                //如果这个字符没有被匹配过，减小要匹配的个数
                if(Tmap[S[r]] > 0) elemCnt--;

                //匹配到对应的字符 
                Tmap[S[r]]--;
            }

            if(elemCnt == 0) {
                
                //滑动窗口大小不为 0， 且不属于要统计的字符或者被统计的字符在当前窗口有冗余 
                while (l < r && ( Tmap.find(S[l]) == Tmap.end() || Tmap[S[l]] < 0 ))
                {
                    //如果为负表示，窗口有当前字符的冗余，当滑动窗口时可以继续向前滑动
                    if(Tmap.find(S[l]) != Tmap.end()) ++Tmap[S[l]];
                    ++l;
                }
                
                //此时 r - l 为 匹配的窗口
                int curWin = (r-l+1);

                //如果小于最小，则更新窗口和起始索引
                if( curWin < winSize)
                {
                    winSize = curWin;
                    bgIdx = l;
                }

                //如果当前窗口的左端字符为 X，继续滑动，用窗口右端寻找下一个 X
                if (l < r) {

                    //增加 X 的要统计的个数                   
                    Tmap[S[l]] = 1;
                    //一次寻找一个
                    elemCnt = 1;
                    ++l;
                }
            }
        }


        if (winSize == INT_MAX) return "";

        return S.substr(bgIdx, winSize);
    }
};