# [76\. Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/)

問題描述：給予兩個字串 `s` 和 `t`，在字串 `s` 中找出包含 `t` 中所有字符的最小子字串。如果 `s` 中不存在這樣的子串，則返回空字串 `""`。

注意事項：

1. 答案必須是 `s` 的子字串，也就是連續的字元序列。
2. 如果有多個符合條件的子字串，只需要返回任意一個。
3. 可以假設 `s` 和 `t` 僅包含英文字母。

解題思路：

1. Sliding Window：使用兩個指標（`left` 和 `right`）來維護一個 Sliding Window。
2. HashMap：使用 HashMap 記錄 t 中字元的出現頻率，以及 Sliding Window 中匹配的字元情況。
3. 擴展和收縮：擴展 `right` 指標找到可行解，然後收縮 `left` 指標優化解。

算法步驟：

1. 初始化 HashMap，記錄 `t` 中每個字元的出現次數。
2. 初始化 `left` 和 `right` 指針，以及用於記錄結果的變數。
3. 移動 `right` 指針，擴大窗口：
- 如果遇到 `t` 中的字符，更新匹配情況。
- 當找到一個包含 `t` 所有字符的窗口時，嘗試收縮。
4. 移動 `left` 指針，縮小窗口：
- 如果可以移除左邊的字元而不影響包含關係，則移除。
- 每次移除時更新最小窗口的資訊。
5. 重複步驟 3 和 4，直到走訪完整個 `s`。
6. 返回找到的最小覆蓋子串，如果沒找到則返回空字串。

:::spoiler Solution

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

        int left = 0;
        
        // 當前窗口中已匹配的字元數量
        int cnt = 0;
        
        // 最小子字串的起始位置
        int minLeft = -1;

        // 最小子字串的長度
        int minLen = INT_MAX;
        
        // 計算字元出現的頻率
        unordered_map<char, int> m;
        for (auto& c : t) ++m[c];

        for (int right = 0; right < s.size(); ++right)
        {
            // 如果 --m[s[right]] >= 0
            // 代表是目標字元，則 ++cnt
            if (--m[s[right]] >= 0)
            {
                ++cnt;
            }

            // 當 cnt == t.size() 的時候，代表子字串都有覆蓋到 t 的字母了
            while (cnt == t.size())
            {
                // 則計算當前的長度
                int curLen = right - left + 1;

                // 如果發現當前的長度更小，則
                if (minLen > curLen)
                {
                    // 更新 minLen 的值
                    minLen = curLen;
                    
                    // 最小左邊界等於 left
                    minLeft = left;
                }

                // 如果發現左邊界是 t 其中一個字母
                // 則頻率 + 1 回來，且計數 cnt - 1
                if (++m[s[left]] > 0) --cnt;
                
                // 最後更新左邊界
                ++left;
            }
        }
        return minLeft == -1 ? "" : s.substr(minLeft, minLen);
    }
};

- 時間複雜度：$O(∣S∣+∣T∣)$
- 空間複雜度：$O(∣S∣+∣T∣)$
:::