# 76 - Minimum Window Substring

解法一 - Sliding window

這個解法跟 #567 和 #438 是一脈相承，主要的差異是在於將 wineowStart 往前移動的條件不一樣，這邊的條件是，只要目前的 window 還包含 pattern 裡的所有字母，就應該要縮減 windowStart，並且在移動過程、得到更小的 substring 時，要更新 res。實作如下：

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> table;
        for(auto c:t)
            table[c]++;

        string res = s;
        res += s;

        int windowStart = 0, matched = 0;
        for(int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char endChar = s[windowEnd];

            if(table.find(endChar) != table.end()) {
                table[endChar]--;
                if(table[endChar] == 0) {
                    matched++;
                }
            }   

            while(matched == table.size()) {
                if(windowEnd - windowStart + 1 < res.length()) {
                    res = s.substr(windowStart, windowEnd - windowStart + 1);
                }

                char startChar = s[windowStart++];
                if(table.find(startChar) != table.end()) {
                    if(table[startChar] == 0)
                        matched--;
                    table[startChar]++;
                }
            }
        }

        return res.length() == s.length()*2 ? "" : res;
    }
};

Time complexity: O(N+M) Space complexity: O(M)