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

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

解法1：滑動(dòng)窗口

public String minWindow(String s, String t) {// 初始化一個(gè)足夠大的數(shù)組來(lái)計(jì)數(shù)字符，假設(shè)字符集大小為70（A-Z的大小寫）int[] cnt = new int[70];// 標(biāo)記是否找到有效子串boolean flag = false;// 遍歷字符串 t，對(duì)每個(gè)字符進(jìn)行計(jì)數(shù)，并將對(duì)應(yīng)的數(shù)組元素減1for (int i = 0; i < t.length(); i++) {char c = t.charAt(i);cnt[c - 'A']--; // 將字符轉(zhuǎn)換為0-65的整數(shù)，便于在數(shù)組中索引}// 初始化結(jié)果字符串為 s，假設(shè)沒(méi)有找到更小的子串String res = s;// 初始化左右指針int l = 0, r = 0;// 滑動(dòng)窗口的右邊界while (r < s.length()) {// 將 s 的當(dāng)前字符計(jì)數(shù)加1cnt[s.charAt(r) - 'A']++;// 當(dāng)前窗口包含 t 的所有字符時(shí)，嘗試收縮左邊界while (l <= r && check(cnt)) {// 標(biāo)記已找到有效子串flag = true;// 更新最小窗口String tmp = s.substring(l, r + 1);res = tmp.length() < res.length() ? tmp : res;// 移動(dòng)左邊界，將 l 所指的字符從計(jì)數(shù)器中減去cnt[s.charAt(l) - 'A']--;l++;}// 擴(kuò)展右邊界，繼續(xù)尋找可能的最小子串r++;}// 如果找到了有效子串，返回 res，否則返回空字符串return flag ? res : "";
}// 檢查數(shù)組中的所有計(jì)數(shù)是否都大于等于0，即 s 的當(dāng)前窗口是否包含 t 的所有字符
public boolean check(int[] arr) {for (int i = 0; i < arr.length; i++) {if (arr[i] < 0)return false; // 如果有字符計(jì)數(shù)小于0，則當(dāng)前窗口不包含 t 的所有字符}return true; // 所有字符計(jì)數(shù)都非負(fù)，說(shuō)明當(dāng)前窗口包含 t 的所有字符
}

定義兩個(gè)長(zhǎng)度為 60（足夠存下所有字母種類）的數(shù)組 c1 和 c2，用于存儲(chǔ)字符頻率。其中 c1 用于記錄字符串 t 中字符的頻率，c2 用于記錄當(dāng)前滑動(dòng)窗口內(nèi)字符的頻率。
設(shè)定好字母與頻率數(shù)組下標(biāo)的映射關(guān)系：小寫字母 a-z 對(duì)應(yīng)下標(biāo) 0-25，大寫字母 A-Z 對(duì)應(yīng)下標(biāo) 26-51。
使用變量 tot 來(lái)記錄還需要匹配的字符種類數(shù)，當(dāng) tot = 0 代表當(dāng)前滑動(dòng)窗口對(duì)應(yīng)的子串能夠?qū)崿F(xiàn)對(duì) t 的覆蓋，即任意字符滿足 c2[i]≥c1[i]。
使用雙指針 j 和 i 表示滑動(dòng)窗口的左右邊界。從前往后遍歷字符串 s，在每個(gè)位置上更新字符頻率數(shù)組 c2。若 c2 中字符的頻率達(dá)到了 c1 中的字符頻率，則將 tot 減 1，表示一個(gè)字符已經(jīng)匹配完成。
每當(dāng)右邊界往后移動(dòng)一步之后，滑動(dòng)窗口會(huì)增加一個(gè)字符。此時(shí)我們檢查左邊界能否右移，同時(shí)不會(huì)使得 tot 變大。即每次右邊界右移后，我們檢查左邊界 c2[j]>c1[j] 是否滿足：

• 若滿足：說(shuō)明當(dāng)前左邊界指向字符并非必須，當(dāng)前子串 s[j…i] 必然不是最短子串。我們讓左邊界 j 進(jìn)行右移，并重復(fù)進(jìn)行左邊界 c2[j]>c1[j] 的檢查，直到窗口不能再收縮
• 若不滿足：說(shuō)明當(dāng)前窗口沒(méi)有任何一個(gè)后綴字符串能夠?qū)崿F(xiàn)對(duì) t 的覆蓋，我們并不能對(duì)窗口實(shí)現(xiàn)收縮

每次對(duì)窗口移動(dòng)完成后，我們檢查當(dāng)前 tot 是否為 0（對(duì)字符串 t 的覆蓋是否完成），若為 0 則嘗試用當(dāng)前窗口對(duì)應(yīng)的字符串 s[j…i] 更新 ans。

class Solution {public String minWindow(String s, String t) {int n = s.length(), tot = 0;int[] c1 = new int[60], c2 = new int[60];for (char x : t.toCharArray()) {if (++c1[getIdx(x)] == 1) tot++;}String ans = "";for (int i = 0, j = 0; i < n; i++) {int idx1 = getIdx(s.charAt(i));if (++c2[idx1] == c1[idx1]) tot--;while (j < i) {int idx2 = getIdx(s.charAt(j));if (c2[idx2] > c1[idx2] && --c2[idx2] >= 0) j++;else break;}if (tot == 0 && (ans.length() == 0 || ans.length() > i - j + 1)) ans = s.substring(j, i + 1);}return ans;}int getIdx(char x) {return x >= 'A' && x <= 'Z' ? x - 'A' + 26 : x - 'a';}
}