LeetCode Minimum Window Substring：滑動窗口尋找最小覆蓋子串

問題描述

給定字符串 S 和目標字符串 T，在 S 中找到包含 T 所有字符的最短子串。要求時間復雜度 O(n)。

例如：
S = "ADOBECODEBANC", T = "ABC"
最小窗口為 "BANC"。

滑動窗口核心思路

維護一個窗口 [left, right]，用哈希表記錄 T 中每個字符的需求數量 need[c]，以及窗口內當前擁有的數量 have[c]。另維護一個計數器 required 表示尚未滿足的字符種類數。

1. 右指針 right 不斷擴展窗口，直到窗口覆蓋所有所需字符（required == 0）。
2. 此時嘗試移動左指針 left 收縮窗口，只要窗口仍覆蓋 T，持續更新最小長度與起始位置。
3. 當窗口不再覆蓋 T，繼續移動 right。

關鍵優化：單次遍歷

不需要額外的 have 表，直接在 need 上修改：
- 遇到目標字符，need[c]--；若 need[c] >= 0 則 required--。
- 移出字符時，need[c]++；若 need[c] > 0 則 required++。
這樣只需一個大小為字符集的數組（如 128 或 256）。

C 實現（原題給出生成式代碼）

char *minWindow(char *S, char *T) {
    int SL = strlen(S), TL = strlen(T);
    bool inT['z' + 1] = {false};
    int need['z' + 1] = {0};
    for (int i = 0; i < TL; ++i) need[T[i]] += inT[T[i]] = true;

    int left = 0, right = -1, bestLeft = 0, bestLen = SL + 1;
    while (right < SL) {
        if (TL == 0) { // 窗口已覆蓋
            if (bestLen > right - left + 1) {
                bestLen = right - left + 1;
                bestLeft = left;
            }
            if (inT[S[left]] && ++need[S[left]] > 0) TL++;
            left++;
        } else { // 擴展右邊界
            if (--need[S[++right]] >= 0 && inT[S[right]]) TL--;
        }
    }
    if (bestLen == SL + 1) return "";
    S[bestLeft + bestLen] = '\0';
    return S + bestLeft;
}

複雜度分析

• 時間：O(|S| + |T|) — 每個指針最多遍歷一次 S。
• 空間：O(|Σ|) — 字符集大小，通常為常數 128/256。

總結

這道題是滑動窗口的經典應用，關鍵在於用單一數組同時維护「需求」與「擁有」，並用一個計數器判斷窗口是否合法，實現真正的 O(n) 線性掃描。