題目與適用情境
給定字串 s 和 t，在 s 中找出一個最短連續子字串，使它包含 t 的每個字元，並達到 t 中對應的 出現次數。字元比對區分大小寫。例如：
s = "ADOBECODEBANC"
t = "ABC"
輸出 = "BANC"t = "AABC" 時，候選視窗必須至少有兩個 A、一個 B 和一個 C。只檢查字元集合會漏掉重複次數， 這是本題最常見的語意錯誤。
限制為 1 <= s.length, t.length <= 100000，字元只包含大小寫英文字母；若答案存在，最短答案唯一。若沒有 任何視窗涵蓋 t，回傳空字串。本文實作也防禦性處理空 t 和 s 比 t 短的輸入，但這兩項不在標準 限制內。
近期公開的軟體工程師面試紀錄中，最小涵蓋子字串仍以原題或「t 中沒有重複字元」的變形出現。中文、英文 線上程式題庫也都保留這道題。核心能力是把全域最短區間轉成可維護的區域狀態，因此歸入 coding；範例 語言不會改變分類。
面試官評估重點
第一層是題意建模。強回答會把「包含 t」寫成頻次限制：對 t 中每個字元 c，目前視窗頻次 window[c] >= need[c]。只說「視窗中出現過這些字元」無法處理 t = "AA"。
第二層是從二次列舉找到單調性。右邊界右移只會增加字元，合法視窗會繼續合法；固定右邊界後，左邊界右移會 逐步刪除字元。視窗一旦合法，就能持續收縮到剛好失效，並在收縮過程記錄最短答案。
第三層是狀態壓縮。每回合掃描整張頻次表會讓複雜度退化。實作以 formed 表示「已有多少種目標字元達到需求 頻次」，並令 required = need.size。某字元的視窗頻次第一次等於需求時，formed 加一；從等於需求降到 少於需求時，formed 減一。超過需求的額外字元不會重複計數。
最後是正確性與邊界。候選人應解釋為何每個右邊界對應的最短合法視窗都會被檢查、為何捨棄的左端點不會 成為未來更好的答案，並正確說明兩個指標各自最多移動 s.length 次的線性複雜度。
回答前需要釐清的問題
- 字元是否區分大小寫？ 本題區分；若產品要求忽略大小寫，應先定義正規化規則，而正規化可能改變回傳
原字串的索引對應。
- 「包含」是否要求順序一致？ 本題只要求頻次涵蓋，字元在視窗內的順序不限；若要求依序出現，問題會變成
最小視窗子序列，目前的滑動視窗條件不再成立。
- 重複字元是否依次數計算？ 是。
t = "AABC"需要兩個A，這直接決定要使用頻次表。 - 最短答案並列時回傳哪一個？ 標準題保證最短答案唯一。若移除此保證，本文程式只在更短時更新，因此會
回傳最早出現的最短視窗。
- 輸入字元集是什麼？ 限制只有大小寫英文字母，所以依 JavaScript UTF-16 code unit 索引不會拆開輸入
字元。若擴充到任意 Unicode，需先定義依 code point 或使用者可見的 grapheme cluster 比對。
- 是否允許空字串？ 標準限制不允許。示範函式把空
t、空s或s.length < t.length都回傳空字串。 - 只回傳子字串，還是也要索引？ 主問題回傳子字串。若需要索引，可回傳
[bestStart, bestStart + bestLength)，核心演算法不變。
這些問題會直接改變合法條件、索引方式或回傳規則。程式語言偏好、變數名稱和雜湊表實作不會改變演算法選擇。
30 秒回答框架
「我會用 need 統計目標頻次，再用左右指標維護視窗。右指標擴張時，某類字元首次達到需求就讓 formed 加一；全部種類滿足後，先記錄答案，再移動左指標直到視窗失效。這樣會檢查每個右邊界對應的最短合法視窗。 兩個指標只向右，每個位置最多進出一次，所以時間是 O(|s| + |t|)，頻次表空間是 O(u)。」
分步深入解答
第一步：用基礎方案找出瓶頸。
固定左端點後，可以持續擴張右端點並維護頻次，遇到第一個合法視窗就記錄。這省去對每個子字串重新統計， 但最壞情況仍會從每個左端點重新掃描，時間為 O(|s|^2 + |t|)。若每個子字串都重新計數，甚至會到三次方。
| 方案 | 時間複雜度 | 額外空間 | 主要成本 | |---|---:|---:|---| | 每個左端點重新向右擴張 | O(|s|^2 + |t|) | O(u) | 相鄰搜尋重複讀取同一字元 | | 每回合掃描全部目標種類判斷合法 | O(|s|u + |t|) | O(u) | 合法性檢查反覆走訪頻次表 | | 滑動視窗加已滿足種類數 | O(|s| + |t|) | O(u) | 必須精準維護跨越門檻的時機 |
這裡的 u 是 t 中不同字元的數量，英文字母限制下最多為 52。線性方案的重點仍是狀態設計，不能用字元集 很小來掩蓋錯誤的合法性判斷。
第二步：定義能以常數時間判斷合法的狀態。
need 保存目標頻次，window 只保存目標字元在目前視窗中的頻次。required = need.size 是需要滿足的字元 種類數；formed 是已經達到需求頻次的種類數。視窗合法若且唯若 formed === required。
更新規則必須圍繞「跨越需求門檻」：
加入 c 後：window[c] 從 need[c]-1 變成 need[c]，formed += 1
加入 c 後：window[c] 從 need[c] 變成 need[c]+1，formed 不變
刪除 c 前：window[c] 等於 need[c]，刪除後會不足，formed -= 1
刪除 c 前：window[c] 大於 need[c]，刪除後仍滿足，formed 不變若把 formed 當成已匹配字元總數，額外出現的字元容易被多算；若每次加入目標字元都加一，又未限制超過需求 的部分，t = "AABC" 很快就會觸發假的合法狀態。
第三步：決定擴張、記錄、收縮的順序。
右指標把 s[right] 納入視窗並更新狀態。視窗合法後進入內層迴圈：先用區間 [left, right] 更新答案，再 準備刪除 s[left]。若刪除會使某種字元不足，先把 formed 減一；接著降低頻次並右移 left。
「先記錄，再刪除」保證目前合法視窗不會被漏掉。「刪除前檢查是否剛好等於需求」能正確反映門檻變化。檢查 也能寫在降低頻次之後，但條件要同步改成「已經小於需求」，程式與說明必須一致。
第四步：實作線性演算法。
export function minWindow(s: string, t: string): string {
if (t.length === 0 || s.length < t.length) return "";
const need = new Map<string, number>();
for (const char of t) {
need.set(char, (need.get(char) ?? 0) + 1);
}
const window = new Map<string, number>();
const required = need.size;
let formed = 0;
let left = 0;
let bestStart = 0;
let bestLength = Number.POSITIVE_INFINITY;
for (let right = 0; right < s.length; right += 1) {
const char = s[right];
const target = need.get(char);
if (target !== undefined) {
const nextCount = (window.get(char) ?? 0) + 1;
window.set(char, nextCount);
if (nextCount === target) formed += 1;
}
while (formed === required) {
const length = right - left + 1;
if (length < bestLength) {
bestStart = left;
bestLength = length;
}
const leftChar = s[left];
const leftTarget = need.get(leftChar);
if (leftTarget !== undefined) {
const currentCount = window.get(leftChar) ?? 0;
if (currentCount === leftTarget) formed -= 1;
window.set(leftChar, currentCount - 1);
}
left += 1;
}
}
return Number.isFinite(bestLength)
? s.slice(bestStart, bestStart + bestLength)
: "";
}實作只為目標字元維護 window。非目標字元仍會影響視窗長度和左邊界，因此不能先從 s 刪除；它們不需要 寫入頻次表。
第五步：寫出不變量與正確性證明。
每次外層迴圈結束時，都維持以下事實：
window[c]等於目前區間[left, right]中目標字元c的實際出現次數。formed精確等於滿足window[c] >= need[c]的目標字元種類數。- 內層迴圈結束後，目前視窗已經失效；剛才列舉過的最後一個合法視窗，是該
right對應的最短合法視窗。 left只向右移動。已略過的更早左端點會形成更長的視窗，未來右邊界繼續右移時，也不會優於已檢查的
同右邊界候選。
初始化時視窗為空，前兩項成立。加入右端字元只依實際頻次更新狀態，門檻規則維持第二項。合法時持續刪除 左端字元；每次刪除前先記錄答案，因此所有以目前 right 結尾的合法候選都被檢查，直到第一、二項共同說明 視窗失效。對所有右邊界歸納，演算法檢查了每個右邊界下的最短合法視窗；全域最短視窗必定是其中之一，因此 最後記錄的就是答案。
第六步：逐步檢查重複字元。
取 s = "AAABBC"、t = "AABC"：
need = {A:2, B:1, C:1}, required = 3
right=0, A:1 formed=0
right=1, A:2 formed=1
right=2, A:3 formed=1 額外 A 不重複計數
right=3, B:1 formed=2
right=4, B:2 formed=2 額外 B 不重複計數
right=5, C:1 formed=3 [0,5] 合法
移除索引 0 的 A 後 A:2，仍合法，記錄 [1,5] = "AABBC"
再移除一個 A 會使 A:1，formed 降為 2，停止收縮這個例子同時檢查三個細節：需求頻次大於一、超過需求的字元不增加 formed、刪除多餘字元後視窗仍可繼續 收縮。
第七步：分析複雜度。
建立 need 會掃描 t 一次。右指標掃描 s 一次，左指標在整個執行中也最多從 0 移到 s.length；內層 while 累計執行 O(|s|) 次。雜湊表操作以平均 O(1) 計算，總時間為 O(|s| + |t|)。兩張頻次表最多 保存 u 個目標字元，額外空間為 O(u)；英文字母限制下 u <= 52。
第八步：用 oracle 和性質驗證。
固定測試至少涵蓋：
("ADOBECODEBANC", "ABC") -> "BANC" 標準混合輸入
("AAABBC", "AABC") -> "AABBC" 重複需求
("a", "a") -> "a" 最小規模
("a", "A") -> "" 大小寫敏感、無解
("abc", "abcd") -> "" s 比 t 短
("abc", "") -> "" 防禦性空目標再為短隨機字串執行二次列舉 oracle。對最佳化結果檢查三個性質：結果確實是 s 的連續子字串；頻次涵蓋 t；沒有更短的涵蓋子字串。差分測試很適合發現 formed 多算、答案長度少一和刪除順序錯誤。
當 s 很短、只需要處理一次且沒有效能要求時，二次列舉更短，也比較容易在面試現場寫對。題目允許長度 100000 並明確要求線性時間時，滑動視窗才是應完成的最終方案。
高品質示範回答
「我先確認這裡的包含依字元頻次計算，順序不限，並且區分大小寫。暴力方法可以固定每個左端點向右擴張， 最壞需要二次時間。這題有單調性：右端加入字元後，合法視窗不會因擴張而失效；視窗合法時，可以移動左端 找出同一右端點下的最短合法視窗。
我會用 need 記錄 t 的頻次，用 window 記錄目前視窗中目標字元的頻次。再維護 formed，表示已經 達到需求頻次的字元種類數。加入字元後，只有頻次剛好達到需求時才增加 formed；視窗合法時先記錄答案， 再刪除左端字元。如果刪除前該字元頻次剛好等於需求，刪除會使視窗失效，因此減少 formed。
關鍵不變量是 window 始終對應 [left, right] 的真實頻次，formed 始終等於已滿足的目標種類數。內層 迴圈會檢查每個右端點對應的所有合法左邊界，停止時剛越過該右端點的最短合法視窗。全域最短答案一定在這些 候選中。右指標和左指標都只向右走，每個位置最多加入和移出一次，所以時間是 O(|s| + |t|)，空間是 O(u)。我會用 t 含重複字元、無解、單一字元、大小寫不同和隨機短字串對照暴力實作來驗證。」
常見錯誤
- 只用集合記錄目標字元 → 無法表達
t中的重複次數 → 使用需求頻次表。 - 每加入一個目標字元就增加匹配數 → 超額字元會產生假的合法狀態 → **只在頻次首次達到需求時增加
formed。**
- 刪除字元後無條件減少
formed→ 刪除多餘副本時視窗仍然合法 → 只有刪除前頻次剛好等於需求才減少。 - 合法後只收縮一次 → 漏掉同一右邊界下更短的視窗 → 用
while收縮到首次失效。 - 先移動左指標再記錄答案 → 可能跳過目前最短合法視窗或造成 off-by-one → 先計算
[left, right]長度。 - 每回合走訪整張
need判斷合法 → 複雜度多出u因子 → 增量維護已滿足種類數。 - 把子字串問題寫成子序列演算法 → 允許跳過區間內位置，回傳結果不再連續 → 視窗始終用連續索引區間表示。
- 先過濾
s的非目標字元，再直接切原字串 → 過濾後索引無法直接對應原字串 → **保留原字串指標，頻次表
只忽略非目標字元。**
- 宣稱內層迴圈導致二次時間 → 忽略左指標全程單調前進 → 依每個位置最多移出一次做累計分析。
- 只驗證標準範例 → 重複需求、無解和大小寫邊界仍可能錯誤 → 加入固定反例與隨機 oracle。
追問與應對
追問一：為什麼 formed 統計字元種類，而不統計已匹配字元總數？
兩種狀態都能設計出正確演算法，但種類計數讓合法條件和門檻變化更清楚。對 need[A] = 2，只有 window[A] 從 1 變成 2 時，這一類才完成；第三個 A 不改變完成狀態。刪除時從 2 降到 1 才撤銷完成。 若統計字元總數，加入時必須使用 window[c] <= need[c] 才增加，刪除時也要對稱維護，條件更容易寫錯。
追問二：如果 t 保證沒有重複字元，可以簡化什麼？
need 的每個值都為 1，window 可以換成目前視窗內目標字元的計數，或集合加計數；但仍要處理同一目標 字元在視窗中出現多次，因為刪除一個副本不一定會使視窗失效。保留通用頻次實作只增加很小的常數，並能直接 處理原題。
追問三：如果要求字元依 t 中的順序出現呢？
這會變成最小視窗子序列。頻次涵蓋已不足以判斷合法，例如 s = "cba"、t = "abc" 的頻次完全涵蓋， 順序卻不成立。可以用動態規劃記錄每個前綴匹配的起點，或對每個候選結尾做向前、向後掃描；需要重新分析 複雜度，本文的 formed === required 條件不能沿用。
追問四：如果要回傳所有並列的最短視窗呢？
移除唯一性保證後，先照常維護 bestLength。發現更短視窗時清空結果並加入目前區間；發現長度等於 bestLength 時追加目前區間。若同一文字區間可能由不同路徑重複發現，還需依 [left, right] 去重；目前 雙指標流程每個區間只會造訪一次，不需要額外集合。
追問五：如果 s 是無法一次放入記憶體的字元流呢？
需求頻次和雙指標狀態仍可在線更新，但回傳原始子字串需要保留目前候選區間。可以用佇列保存從 left 到最新 位置的字元及全域位移；視窗長期無法滿足時，快取可能接近整個已讀資料流。若只回傳長度和位移，儲存壓力可 依目標字元位置進一步壓縮；若必須回傳文字，需要明確定義最大視窗或外部儲存策略。
追問六：如何支援任意 Unicode 文字？
先約定比對單位。依 Unicode code point 比對時，可使用 Array.from 或 code point iterator，並同時保存原 字串的 code unit 位移以便切片。使用者可見字元可能由多個 code point 組成；若要求依 grapheme cluster 比對，需要可靠的分段器。正規化形式也會影響「相同字元」的定義，必須在建立頻次表前統一處理，並保留到 原文字的對應規則。
追問七：如何證明隨機測試的 oracle 本身可信？
oracle 只用於短字串，可以列舉所有 [left, right]，為每個區間直接重新統計頻次，再依長度和起點選擇 答案。它刻意使用與最佳化演算法不同的控制流程，雖然複雜度高，但邏輯直接。固定測試先驗證 oracle；隨機 差分再比較答案長度、連續性和涵蓋頻次，降低兩個實作共享同一錯誤的機率。