【重点!!!】【滑动窗口】76.最小覆盖子串

题目
思路参考《算法小抄》
滑动窗口典型题目！！！

Python

参考：灵茶山艾府

写法1

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ans_left, ans_right = -1, len(s)
        cntS = Counter()
        cntT = Counter(t)

        left = 0
        for right, x in enumerate(s):
            cntS[x] += 1
            while cntS >= cntT:
                if right - left < ans_right - ans_left:
                    ans_left, ans_right = left, right
                cntS[s[left]] -= 1
                left += 1

        return s[ans_left: ans_right+1] if ans_left >= 0 else ""

写法2

这版代码结合《算法小抄》更容易理解！！！

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        window, need = [0] * 256, [0] * 256
        for c in t:
            need[ord(c)] += 1
        
        l, r, valid = 0, 0, 0
        start_idx, min_len = -1, len(s) + 1
        t_set = set(list(t))
        for r in range(len(s)):
            new_char = s[r]
            r += 1
            if new_char in t_set:
                window[ord(new_char)] += 1
                if window[ord(new_char)] == need[ord(new_char)]:
                    valid += 1
            
            while valid == len(t_set):
                if r - l < min_len:
                    min_len = r - l
                    start_idx = l
                del_char = s[l]
                l += 1
                if window[ord(del_char)] > 0:
                    if window[ord(del_char)] == need[ord(del_char)]:
                        valid -= 1
                    window[ord(del_char)] -= 1

        return '' if start_idx == -1 else s[start_idx: start_idx + min_len]

另外1版代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        start_idx = -1
        min_len = len(s) + 1
        t_set = set(list(t))
        s_arr = [0] * 256
        t_arr = [0] * 256
        for i in range(len(t)):
            t_arr[ord(t[i])] += 1
        
        l = r = 0
        valid = 0
        for r in range(len(s)):
            new_char = s[r]
            r += 1
            if new_char in t_set:
                s_arr[ord(new_char)] += 1
                if s_arr[ord(new_char)] == t_arr[ord(new_char)]:
                    valid += 1
            
            while valid == len(t_set):
                if r - l < min_len:
                    min_len = r - l
                    start_idx = l
                del_char = s[l]
                l += 1
                if s_arr[ord(del_char)] > 0:
                    if s_arr[ord(del_char)] == t_arr[ord(del_char)]:
                        valid -= 1
                    s_arr[ord(del_char)] -= 1

        if start_idx == -1:
            return ''
        else:
            return s[start_idx: start_idx + min_len]

Java

法1：使用数组代替Map

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[256];
        int[] window = new int[256];
        Set<Character> usedSet = new HashSet<>();
        int left = 0, right = 0, valid = 0, start = 0, minLen = Integer.MAX_VALUE;
        for (char c : t.toCharArray()) {
            need[c]++;
            usedSet.add(c);
        }
        while (right < s.length()) {
            char curChar = s.charAt(right);
            ++right;
            if (need[curChar] > 0) {
                window[curChar]++;
                if (window[curChar] == need[curChar]) {
                    valid++;
                }
            }
            while (valid == usedSet.size()) {
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                char deleteChar = s.charAt(left);
                left++;
                if (window[deleteChar] > 0) {
                    if (window[deleteChar] == need[deleteChar]) {
                        --valid;
                    }
                    window[deleteChar]--;
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

class Solution {
    public String minWindow(String s, String t) {
        int startIndex = -1, endIndex = s.length(), valid = 0, left = 0, right = 0;
        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();
        int[] need = new int[256];
        int[] window = new int[256];
        Set<Character> set = new HashSet<>();
        for (char c : tArray) {
            set.add(c);
            ++need[c];
        }
        while (right < sArray.length) {
            char c = sArray[right];
            ++right;
            if (!set.contains(c)) {
                continue;
            }
            ++window[c];
            if (window[c] == need[c]) {
                ++valid;
            }
            while (valid == set.size() && left < right) {
                if (right - left < endIndex - startIndex) {
                    startIndex = left;
                    endIndex = right;
                }
                char d = sArray[left];
                ++left;
                if (!set.contains(d)) {
                    continue;
                } else {
                    if (window[d] == need[d]) {
                        --valid;
                    }
                    --window[d];
                }
            }
        }

        return startIndex == -1 ? "" : s.substring(startIndex, endIndex);
    }
}

法2：使用HashMap

注意：Integer比较使用equals！！！不要用 “" ！！！
注意：Integer比较使用equals！！！不要用 "”！！！
注意：Integer比较使用equals！！！不要用"=="！！！

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0) {
            return new String("");
        }
        Map<Character, Integer> charToCountMap = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (int i = 0; i < t.length(); ++i) {
            charToCountMap.put(t.charAt(i), charToCountMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = 0, right = 0, valid = 0, start = 0, minLen = Integer.MAX_VALUE;
        while (right < s.length()) {
            char curChar = s.charAt(right);
            ++right;
            if (charToCountMap.containsKey(curChar)) {
                window.put(curChar, window.getOrDefault(curChar, 0) + 1);
                if (window.get(curChar).equals(charToCountMap.get(curChar))) {
                    ++valid;
                }
            }
            while (valid == charToCountMap.size()) {
                if (right - left < minLen) {
                    start = left; 
                    minLen = right - left; // 注意: 这里right已经自增过了
                }
                char removeChar = s.charAt(left);
                ++left;
                if (window.containsKey(removeChar)) {
                    if (window.get(removeChar).equals(charToCountMap.get(removeChar))) {
                        --valid;
                    }
                    window.put(removeChar, window.get(removeChar) - 1);
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}