76. Minimum Window Substring

真的好難啊哈哈

這應該是滑動窗口的新境界, 我根本沒辦法想到

首先先把t所有的字母, 加到hashtable,

然後我們開始遍歷s,

我們遍歷的時候, 會先減去在table裡的值, 倘若剪去後, 值還大於等於0, 代表這個值是有存在在t裡, 用一個count紀錄, 持續收收到count == t.size() 代表所有值都已被收編, 接著我們就要開始結算, i — left + 1是否小於minLen, 有的話我們就更新,

再來是這邊的第二的精華, 要怎麼改左邊的index,

我們先讓在table 增加這個left值的次數, 假設大於1, 代表他曾是t的一員, 我們要把count給減1, 因為有一個t的成員出去了, 如果不是t的一員, 我們可以簡化掉他, 這樣一來minLen又可以再縮小, left就可以往右移一格, 然後重複判斷直到回圈結束, 直到找到t的一員破壞這個規則

整理下來其實也是不難, 但要想到這樣做其實還蠻多層次的

class Solution {
public:
    
    string minWindow(string s, string t) {
        string res = "";
        unordered_map<char, int> m;
        int left = 0;
        int count = 0;
        int minLen = INT_MAX;
        for(auto c: t){
            m[c]++;
        }
        for(int i = 0;i < s.size();i++){
            m[s[i]]--;
            if(m[s[i]] >= 0) count++;
            while(count == t.size()){
                if(minLen  > i - left + 1){
                    minLen = i - left + 1;
                    res = s.substr(left, minLen);
                }
                m[s[left]]++;
                if(m[s[left]] > 0) count--;
                left++;
            }
        }
        return res;
    }
};