題目網址：https://leetcode.cn/problems/minimum-window-substring/

題意：給兩 string s 和 t, 返回 s 中包含 t 所有 character 的最小 substring。若不存在這樣的 substring, 則返回 empty string ""。

s 和 t 由英文字母組成。

進階：設計 $O(n)$ time 的演算法。

Solution：

想法：利用 Sliding Window, 用兩個 pointer left 和 right, 其中 right 用來擴充 window, 而 left 用來收縮 window

  • 若 window 中的元素不包含 t, 則 right 不斷向右移動, 直到 window 中每種元素的個數 ≥ t 中對應元素的個數
  • left 會不斷收縮, 並更新 res, 直到當 window 中某種元素的個數 < t 中該種元素的個數
    • have 用來記錄符合 window 中某一種元素的個數 == t 中該種元素的個數 之元素個數
    • need 則是記錄 t 中有多少種元素
    • 若 have == need 代表 window 中每種元素的個數 ≥ t 中對應元素的個數

e.g. s = "ADOBECODEBANC", t = "ABC"

  • s 第一次包含 t 之 substring 為 ADOBEC ➔ left = 0, right = 5, curLen = 6, resLen = 6
  • 將左邊之 A pop 掉後, DOBEC 並不包含 t, 因此跳出 while loop, 讓 right 繼續右移, 直到 substring 為 DOBECODEBA ➔ left = 1, right = 10, curLen = 10, resLen = 6
  • 將左邊之 D、O、B、E pop 掉後, 此時 substring 為 CODEBA ➔ left = 5, right = 10, curLen = 6, resLen = 6
  • 將左邊之 C pop 掉後, ODEBA 並不包含 t, 因此跳出 while loop, 讓 right 繼續右移, 直到 substring 為 ODEBANC ➔ left = 6, right = 12, curLen = 7, resLen = 6
  • 將左邊之 O、D、E pop 掉後, substring 為 BANC ➔ left = 9, right = 12, curLen = 4, resLen = 4
  • 將左邊之 B pop 掉後, ANC 並不包含 t, 因此跳出 while loop, 但 right 已到結尾, 無法再右移, 故返回 BANC
class Solution {
public:
    string minWindow(string s, string t) {
        if (t.size() > s.size()) {
            return "";
        }

        unordered_map<char, int> window, cntT;
        for (const auto& ch : t) {
            ++cntT[ch];
        }

        string res;
        int left = 0, resLen = INT_MAX;
        int have = 0, need = cntT.size();

        for (int right = 0; right < s.size(); ++right) {
            const auto rightChar = s[right];
            ++window[rightChar];

            // 在 t 中存在, 且 window 中該元素的個數 >= t 中的個數
            if (cntT.find(rightChar) != cnt.end() && window[rightChar] == cntT[rightChar]) {
                ++have;
            }

            // 一旦 window 中某種元素的個數 < t 中該種元素的個數, 則跳出 while loop
            while (have == need) {
                // 更新 res
                int curLen = right - left + 1;
                if (curLen < resLen) {
                    resLen = curLen;
                    res = s.substr(left, resLen);
                }

                // left 收縮
                const auto leftChar = s[left];
                --window[leftChar];
                if (cntT.find(leftChar) != cnt.end() && window[leftChar] < cntT[leftChar]) {
                    --have;
                }
                ++left;
            }
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 每個 char 最多被拜訪兩次（left, right）
  • space：$O(1)$ ➔ window、cntT 長度不超過 52（大、小寫各 26）