Leetcode刷題76. 最小覆寫子串

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

注意：如果 s 中存在這樣的子串，我們保證它是唯一的答案，

示例 1：

輸入：s = "ADOBECODEBANC", t = "ABC"
輸出："BANC"
示例 2：

輸入：s = "a", t = "a"
輸出："a"

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-window-substring
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

感謝labuladong大神，傳送門我寫了套框架，把滑動視窗演算法變成了默寫題，

class Solution {
        public String minWindow(String s, String t) {
            if (s == null || s.length() == 0 || t == null || t.length() == 0) return "";
//            return minWindowI(s, t);
            return minWindowII(s, t);
        }

        //方法二：使用陣列保存字串
        //時間復雜度O(mn)
        private String minWindowII(String s, String t) {
            //字符本質上是ASCII碼（純英文字符），所以這里用的是該字符的ASCII碼作為下標索引
            int[] need = new int[256];
            int[] window = new int[256];

            for (char c : t.toCharArray()) {
                need[c]++;
            }
            int left = 0, right = 0;
            //統計目前視窗中已經找到了多少個字符
            int valid = 0;
            //start為涵蓋t中所有字符的子串在s中開始的位置，len為子串的長度
            int start = 0, len = Integer.MAX_VALUE;
            char[] str = s.toCharArray();
            while (right < str.length) {
                char c = str[right];
                //向右移動
                right++;
                window[c]++;

                //更新視窗資料
                //need[c]>0表示遇到t中字符，大于等于window[c]是滿足t中字符出現的次數
                if (need[c] > 0 && need[c] >= window[c]) {
                    valid++;
                }

                //開始收縮視窗
                while (valid == t.length()) {
                    //在視窗收縮的時候更新left和len
                    if (right - left < len) {
                        start = left;
                        len = right - left;
                    }

                    char d = str[left];
                    //向左移動
                    left++;

                    //更新視窗資料
                    if (need[d] > 0 && need[d] >= window[d]) {
                        valid--;
                    }
                    window[d]--;
                }
            }
            return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
        }

        //方法一：使用HashMap定義兩個視窗分別保存字串t和字串s中字符出現的次數
        //時間復雜度O(mn)，n是s的長度
        //空間復雜度O(m)，m為t的長度
        private String minWindowI(String s, String t) {
            Map<Character, Integer> need = new HashMap<>();
            Map<Character, Integer> window = new HashMap<>();

            for (char c : t.toCharArray()) {
                need.put(c, need.getOrDefault(c, 0) + 1);
            }
            int left = 0, right = 0;
            //當valid=need.size()時，需要收縮視窗
            int valid = 0;
            //start為涵蓋t中所有字符的子串在s中開始的位置，len為子串的長度
            int start = 0, len = Integer.MAX_VALUE;
            char[] str = s.toCharArray();
            while (right < str.length) {
                char c = str[right];
                //向右移動
                right++;

                //更新視窗資料
                if (need.containsKey(c)) {
                    window.put(c, window.getOrDefault(c, 0) + 1);

                    //視窗中字符的個數滿足字串t中字符的個數
                    if (window.get(c).equals(need.get(c))) {
                        valid++;
                    }
                }

                //開始收縮視窗
                while (valid == need.size()) {
                    //在視窗收縮的時候更新left和len
                    if (right - left < len) {
                        start = left;
                        len = right - left;
                    }

                    char d = str[left];
                    //向左移動
                    left++;

                    //更新視窗資料
                    if (need.containsKey(d)) {
                        if (window.get(d).equals(need.get(d))) {
                            valid--;
                        }
                        window.put(d, window.get(d) - 1);
                    }
                }
            }
            return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
        }
    }