76. 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. 返回找到的最小覆蓋子串，如果沒找到則返回空字串。

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);
    }
};

• T: $O(∣S∣+∣T∣)$
• S: $O(∣S∣+∣T∣)$