76. Minimum Window Substring

// 76. Minimum Window Substring
class Solution_76 {
public:

    //1) begin开始指向0， end一直后移，直到begin - end区间包含T中所有字符。记录窗口长度d
    //2) 然后begin开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被包含在窗口，
    //3) 继续后移end，直到T中的所有字符被包含在窗口，重新记录最小的窗口d。
    //4) 如此循环知道end到S中的最后一个字符。
    //时间复杂度为O(n)
    string minWindow_(string s, string t) {

        string result;
        if (s.empty()||s.size()return result;
        }
        unordered_mapchar, int> mp; //存储t中的字符，便于与s匹配
        int left = 0;
        int cnt = 0;                 //窗口字符串进行计数
        int minlen = s.size()+1;
        for (int i = 0; i for (int right = 0; right if (mp.find(s[right])!=mp.end()) //t字符在left~right窗口
            {
                if (mp[s[right]]>0) //体会>0的作用：当s中有重复字符串时，第一次匹配
                {
                    cnt++; //计数器+1
                }
                mp[s[right]]--; //有重复元素时候，可能减为负
                while (cnt==t.size()) ////当窗口内有t的所有字符，就要开始移动左窗口
                {
                    if (mp.find(s[left])!=mp.end())
                    {
                        if (minlen>right-left+1)
                        {
                            minlen = right - left + 1;
                            result = s.substr(left, right - left + 1);
                        }
                        mp[s[left]]++; //将其包含在mp内，继续查找
                        if (mp[s[left]]>0)
                        {
                            cnt--;
                        }
                    }
                    left++; //右移窗口左边
                }
            }
        }

        return result;
    }

    string minWindow(string S, string T) {
        string S, T;
        return minWindow_(S, T);
    }
};