76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

 

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

解析

我们直接按照滑动窗口的思想，如果满足了条件就缩小窗口，不满足就扩大窗口。

import java.util.*;

class Solution {
    /**
     用滑动窗口的思路来做，先把 left 置零，然后向右移动 right 扩大窗口，找到一个容纳了 t 里所有字符的子串后，记住当前的 left 和 right 为最小子串，然后开始重复以下过程：

     ①右移 left 缩小窗口

     ②检查新的子串是否满足条件，若满足，检查当前子串是否比已找到的最小子串短，按需更新最小子串后，回到①；若不满足，改为扩大窗口，跳到③

     ③右移 right 扩大窗口，若未超出 s 的右边界，继续执行④，否则跳到⑤

     ④检查新的子串是否满足条件，若满足，改为缩小窗口，跳到①；若不满足，回到③继续扩大窗口

     ⑤返回找到的最小子串。
     */
    public String minWindow(String s, String t) {
        String res = "";
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> chars = new HashMap<>();
        int len1 = s.length(), len2 = t.length();
        for(int i = 0; i < len2; i++) {
            char ch = t.charAt(i);
            chars.put(ch, chars.getOrDefault(ch, 0) + 1);
        }
        int left = 0, right = 0, min = Integer.MAX_VALUE;
        while(right < len1) {
            char ch1 = s.charAt(right);
            window.put(ch1, window.getOrDefault(ch1, 0) + 1);
            while(check(window, chars)) {
                if((right - left + 1) < min) {
                    min = right - left + 1;
                    res = s.substring(left, right + 1);
                }
                char ch2 = s.charAt(left);
                window.put(ch2, window.get(ch2) - 1);
                if(window.get(ch2) == 0) {
                    window.remove(ch2);
                }
                left++;
            }
            right++;
        }
        return res;
    }

    //当前窗口是否符合题目条件
    public boolean check(Map<Character, Integer> window, Map<Character, Integer> chars) {
        for(char ch : chars.keySet()) {
            int count = window.getOrDefault(ch,-1);
            if(count<chars.get(ch)) return false;
        }
        return true;
    }
}

注意：本文归作者所有，未经作者允许，不得转载