最小覆蓋子串

難度 - 困難
原題鏈接 - 最小覆蓋字串

給你一個(gè)字符串 s 、一個(gè)字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 “” 。
注意：
對(duì)于 t 中重復(fù)字符，我們尋找的子字符串中該字符數(shù)量必須不少于 t 中該字符數(shù)量。
如果 s 中存在這樣的子串，我們保證它是唯一的答案。

示例 1：
輸入：s = “ADOBECODEBANC”, t = “ABC”
輸出：“BANC”
解釋：最小覆蓋子串 “BANC” 包含來(lái)自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

示例 2：
輸入：s = “a”, t = “a”
輸出：“a”
解釋：整個(gè)字符串 s 是最小覆蓋子串。

示例 3:
輸入: s = “a”, t = “aa”
輸出: “”
解釋: t 中兩個(gè)字符 ‘a(chǎn)’ 均應(yīng)包含在 s 的子串中，
因此沒(méi)有符合條件的子字符串，返回空字符串。

提示：
m == s.length
n == t.length
1 <= m, n <= 1e5
s 和 t 由英文字母組成

滑動(dòng)窗口

這個(gè)算法技巧的思路非常簡(jiǎn)單，就是維護(hù)一個(gè)窗口，不斷滑動(dòng)，然后更新答案么.
該算法的大致邏輯如下：

int left = 0, right = 0;while (left < right && right < s.size()) {// 增大窗口window.add(s[right]);right++;while (window needs shrink) {// 縮小窗口window.remove(s[left]);left++;}
}

這個(gè)算法技巧的時(shí)間復(fù)雜度是 O(N)，比字符串暴力算法要高效得多。

本題的解題思路：
1、我們?cè)谧址?S 中使用雙指針中的左右指針技巧，初始化 left = right = 0，把索引左閉右開(kāi)區(qū)間 [left, right) 稱為一個(gè)「窗口」。
理論上你可以設(shè)計(jì)兩端都開(kāi)或者兩端都閉的區(qū)間，但設(shè)計(jì)為左閉右開(kāi)區(qū)間是最方便處理的。因?yàn)檫@樣初始化 left = right = 0 時(shí)區(qū)間 [0, 0) 中沒(méi)有元素，但只要讓 right 向右移動(dòng)（擴(kuò)大）一位，區(qū)間 [0, 1) 就包含一個(gè)元素 0 了。如果你設(shè)置為兩端都開(kāi)的區(qū)間，那么讓 right 向右移動(dòng)一位后開(kāi)區(qū)間 (0, 1) 仍然沒(méi)有元素；如果你設(shè)置為兩端都閉的區(qū)間，那么初始區(qū)間 [0, 0] 就包含了一個(gè)元素。這兩種情況都會(huì)給邊界處理帶來(lái)不必要的麻煩。

2、我們先不斷地增加 right 指針擴(kuò)大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3、此時(shí)，我們停止增加 right，轉(zhuǎn)而不斷增加 left 指針縮小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同時(shí)，每次增加 left，我們都要更新一輪結(jié)果。

4、重復(fù)第 2 和第 3 步，直到 right 到達(dá)字符串 S 的盡頭。

這個(gè)思路其實(shí)也不難，第 2 步相當(dāng)于在尋找一個(gè)「可行解」，然后第 3 步在優(yōu)化這個(gè)「可行解」，最終找到最優(yōu)解，也就是最短的覆蓋子串。左右指針輪流前進(jìn)，窗口大小增增減減，窗口不斷向右滑動(dòng)，這就是「滑動(dòng)窗口」這個(gè)名字的來(lái)歷。

下面畫(huà)圖理解一下，needs 和 window 相當(dāng)于計(jì)數(shù)器，分別記錄 T 中字符出現(xiàn)次數(shù)和「窗口」中的相應(yīng)字符的出現(xiàn)次數(shù)。

代碼

public String minWindow1(String s, String t) {// 用于記錄需要的字符和窗口中的字符及其出現(xiàn)的次數(shù)Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();// 統(tǒng)計(jì) t 中各字符出現(xiàn)次數(shù)for (char c : t.toCharArray())need.put(c, need.getOrDefault(c, 0) + 1);int left = 0, right = 0;int valid = 0; // 窗口中滿足需要的字符個(gè)數(shù)// 記錄最小覆蓋子串的起始索引及長(zhǎng)度int start = 0, len = Integer.MAX_VALUE;while (right < s.length()) {// c 是將移入窗口的字符char c = s.charAt(right);// 擴(kuò)大窗口right++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) + 1);if (window.get(c).equals(need.get(c)))valid++; // 只有當(dāng) window[c] 和 need[c] 對(duì)應(yīng)的出現(xiàn)次數(shù)一致時(shí)，才能滿足條件，valid 才能 +1}// 判斷左側(cè)窗口是否要收縮while (valid == need.size()) {// 更新最小覆蓋子串if (right - left < len) {start = left;len = right - left;}// d 是將移出窗口的字符char d = s.charAt(left);// 縮小窗口left++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新if (need.containsKey(d)) {if (window.get(d).equals(need.get(d)))valid--; // 只有當(dāng) window[d] 內(nèi)的出現(xiàn)次數(shù)和 need[d] 相等時(shí)，才能 -1window.put(d, window.get(d) - 1);}}}// 返回最小覆蓋子串return len == Integer.MAX_VALUE ?"" : s.substring(start, start + len);}

上期經(jīng)典

leetcode59. 螺旋矩陣 II