76. 最小覆蓋子串

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

 

注意：

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

 

示例 1：

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

示例 2：

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

示例 3:

輸入: s = "a", t = "aa"
輸出: ""
解釋: t 中兩個字符 'a' 均應包含在 s 的子串中，
因此沒有符合條件的子字符串，返回空字符串。

 

提示：

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s 和 t 由英文字母組成


class Solution {
    public String minWindow(String s, String t) {
        int[]need = new int[128];
        for(char c:t.toCharArray()){
            need[c]++;
        }
        // 定義滑動窗口左右指針，收縮和擴張
        int left = 0;
        int right = 0;
        // 當前滿足條件的字符串的長度，找最小
        int minLen = Integer.MAX_VALUE;
        // 結束滿足條件，t 中還需要尋找的字符串數量
        int needcount = t.length();
        // 最小字串起始位置，後續結合 minLen 計算最短字符串
        int start=0;
         // 右指針不斷向右擴張
        while(right<s.length()){
            char sCharAtRight = s.charAt(right);
            // 如果找到還需要的字符
            if(need[sCharAtRight]>0){
                needcount--;
            }
            // 所需字符減一，可以為負數，表示多餘該字符
            need[sCharAtRight]--;
            // 窗口擴張
            right++;
            // 所有需要字符都已經找到，開始收縮左指針
            while(needcount==0){
                // 更新最短字符串
                if(right-left<minLen){
                    minLen = right-left;
                    start = left;
                }
                char sCharAtLeft = s.charAt(left);
                // 所需字符加一
                need[sCharAtLeft]++;
                // 説明少了一個所需字符串，數量加 1
                if(need[sCharAtLeft]>0){
                    needcount++;
                }
                // 窗口收縮
                left++;
            }
        }
        if(minLen==Integer.MAX_VALUE){return "";}
        return s.substring(start,start+minLen);
    }
}