1. 題目鏈接

76. 最小覆蓋子串 - 力扣（LeetCode）

2. 題目描述

給你一個字符串 s 、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 "" 。

注意：

• 對于 t 中重復字符，我們尋找的子字符串中該字符數量必須不少于 t 中該字符數量。
• 如果 s 中存在這樣的子串，我們保證它是唯一的答案。

3. 題目示例

示例 1 :

輸入：s = "ADOBECODEBANC", t = "ABC"
輸出："BANC"
解釋：最小覆蓋子串 "BANC" 包含來自字符串 t 的 'A'、'B' 和 'C'。

示例 2 :

輸入：s = "a", t = "a"
輸出："a"
解釋：整個字符串 s 是最小覆蓋子串。

4. 解題思路

1. 問題理解：
   • 給定一個字符串 S 和一個字符串 t，需要在 S 中找到包含 t 所有字符的最短子串。
   • 子串必須包含 t 的所有字符，且字符的出現次數不少于 t 中的出現次數。
2. 關鍵思路：
   • 滑動窗口：使用雙指針（left 和 right）維護一個窗口，通過移動指針動態調整窗口大小。
   • 哈希表統計：使用數組 cntS 和 cntT 分別統計窗口內字符和 t 中字符的出現次數。
   • 窗口有效性檢查：通過 isCovered 方法檢查當前窗口是否滿足條件。
3. 算法流程：
   • 初始化 cntT 數組，統計 t 中字符的出現次數。
   • 使用雙指針 left 和 right 遍歷 S：
     • right 右移，擴展窗口，更新 cntS。
     • 當窗口滿足條件時，嘗試收縮 left 指針，尋找更小的窗口。
     • 記錄最小窗口的左右邊界。
   • 返回最小窗口對應的子串。

5. 題解代碼

class Solution {public String minWindow(String S, String t) {char[] s = S.toCharArray(); // 將字符串S轉為字符數組int m = s.length; // 字符串S的長度int ansLeft = -1; // 記錄最小窗口的左邊界，初始為-1表示未找到int ansRight = m; // 記錄最小窗口的右邊界，初始為m（字符串長度）// cntS數組記錄當前窗口內各字符的出現次數int[] cntS = new int[128]; // ASCII碼范圍0-127// cntT數組記錄字符串t中各字符的出現次數int[] cntT = new int[128];// 初始化cntT數組for (char c : t.toCharArray()) {cntT[c]++;}int left = 0; // 滑動窗口的左指針for (int right = 0; right < m; right++) { // 滑動窗口的右指針cntS[s[right]]++; // 將右指針指向的字符加入窗口// 檢查當前窗口是否包含t的所有字符while (isCovered(cntS, cntT)) { // 如果當前窗口比之前記錄的最小窗口更小if (right - left < ansRight - ansLeft) { ansLeft = left; // 更新最小窗口的左邊界ansRight = right; // 更新最小窗口的右邊界}cntS[s[left]]--; // 將左指針指向的字符移出窗口left++; // 左指針右移}}// 如果找到了符合條件的窗口，返回對應的子串；否則返回空字符串return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);}// 檢查cntS是否包含cntT的所有字符（即cntS中各字符的數量都不小于cntT）private boolean isCovered(int[] cntS, int[] cntT) {// 檢查大寫字母for (int i = 'A'; i <= 'Z'; i++) {if (cntS[i] < cntT[i]) {return false;}}// 檢查小寫字母for (int i = 'a'; i <= 'z'; i++) {if (cntS[i] < cntT[i]) {return false;}}return true;}
}

6. 復雜度分析

1. 時間復雜度：
   • 遍歷 S 的時間復雜度為 O(m)，其中 m 是 S 的長度。
   • isCovered 方法的時間復雜度為 O(1)（因為字符集大小固定為52個字母）。
   • 總體時間復雜度為 O(m)。
2. 空間復雜度：
   • cntS 和 cntT 數組的大小為 O(128) = O(1)。
   • 其他變量占用常數空間。
   • 總體空間復雜度為 O(1)。