題目描述:給定字串 s 和 t,找出 s 中包含 t 所有字元(含重複)的最小視窗子字串。
解題思路:滑動視窗 + 頻率計數。維護兩個計數器:need(t 中各字元的需求數)和 window(當前視窗內各字元的數量)。變數 have 記錄已滿足需求的字元種數,required 為 t 中不同字元的種數。右指標擴展視窗(have 增加);當 have == required 時記錄答案,然後縮小左指標。
時間複雜度:O(|s| + |t|) — 每個字元最多進出視窗各一次。
空間複雜度:O(|t|) — 需求和視窗計數器的字元集大小。
1. Build frequency map for t (need[]) 2. left=0, have=0, required=distinct chars in t 3. Expand right pointer: a. Add s[right] to window b. If s[right] is needed and window count meets need: have++ 4. While have == required: a. Update min window if smaller b. Remove s[left] from window, advance left c. If removal breaks a requirement: have-- 5. Return min window substring
暴力法 O(n²|Σ|):嘗試所有子串,檢查是否包含 t 中所有字符 — 太慢。
固定右端點 DP O(n|Σ|):對每個右端點,二分搜尋最左有效位置 — 同時間複雜度但常數更差。