76. Minimum Window Substring

解題思路

很容易聯想到 sliding window，若該 window 中所有字母出現次數與希望的一樣，就看長度決定是否更新。

比對的方式則是該兩個 index  array 以及 have 跟 need 兩個 int。index array 用來記錄該字母的出現次數，need 表示需要幾個「字母」種類(不考慮次數)，have 表示現階段的 sliding window 有幾個「字母」(同樣不考慮次數)。

那要怎麼移動 sliding window？暴力解是 O(n^2) 的方法，也就是每個字母依序當開頭，然後每次就開頭 + 1、開頭 + 2的一路看到最後。但有時若已經 valid ，那就可以提前結束。

至此還可以進一步優化。當找到新的 valid window，可以回過頭把 left 往右移，一直到 invalid 為止，這麼做是因為可能前面包含到多餘的子字串。記得這個 pop 的動作也要檢查 have 是否要減少。

程式碼 

class Solution {
public:
    string minWindow(string s, string t) {
        if(t.size() > s.size()) return "";

        int countS[128] = {0}, countT[128] = {0}, left = 0, right = 0;
        int have = 0, need = 0, minLen = s.size()+1, minL = 0, minR = 0;
        bool isFind = false;
        for(int i=0; i<t.size(); i++)
        {
            countT[t[i]]++;
            if(countT[t[i]] == 1) // meet first time
                need++;
        }

        while(right < s.size())
        {
            // add right element into countS
            countS[s[right]]++;
            // check countS[i] == countT[i] ?
                // if true, have++
            if(countS[s[right]] == countT[s[right]])
                have++;
            // check have == need?
                // if true, update window len if needed
                // pop from front until have != need
            while(have == need)
            {
                if((right - left + 1) < minLen)
                {
                    minLen = right - left + 1;
                    minL = left;
                    minR = right;
                    isFind = true;
                }
                countS[s[left]]--;
                if(countS[s[left]] < countT[s[left]])
                    have--;
                left++;
            }
            right++;
        }
        if(!isFind) return "";
        return s.substr(minL, minLen);
    }
};