76. 最小覆盖子串(困难)

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

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

示例 1：

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

示例 2：

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

提示：

1 <= s.length, t.length <= 10<sup>5
s 和 t 由英文字母组成

来源：力扣（LeetCode）

https://leetcode-cn.com/problems/minimum-window-substring/

思路：

滑动窗口模板

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    public String minWindow(String s, String t) {
        //滑动窗口
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        //统计t中各元素个数
        //for(int i =0 ;i<t.length();i++){
        //    Character key = t.charAt(i);
        //    need.put(key,need.getOrDefault(key,0)+1);
        //}
        for(char c : t.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        //开始定义窗口双指针
        int left =0,right=0;
        int count = 0;//这个用来记录
        int len = Integer.MAX_VALUE;
        int start = 0;
        while(right<s.length()){
            //获取移入窗口的值
            char c = s.charAt(right);
            right++;
            //窗口更新
            //如果移入的值在所需的字符串中
            if(need.containsKey(c)){
                //窗口+1
                window.put(c,window.getOrDefault(c,0)+1);
                //如果需要的个数正好满足
                if(window.get(c).equals(need.get(c))){
                    count++;
                }
            }
            //确定左边是否要收缩
            while (count==need.size()){

                //判断长度是否可以更新
                if(right-left<len){
                    //需要记录一下开始的索引
                    start = left;
                    len = right-left;
                }
                //移动左边，窗口缩小
                char c1 = s.charAt(left);
                left++;
                //开始更新窗口内容
                //如果当前要移动的字符是包含在need中，我们需要进行讨论，如果该字符的次数刚好与我们需要的次数相等，则valid--，并同时更新window中这个值出现的次数
                if(need.containsKey(c1)){
                    //左边有重复的
                    if(window.get(c1).equals(need.get(c1))){
                        count--;
                    }
                    window.put(c1,window.getOrDefault(c1,0)-1);
                }
            }
        }
        //返回
        return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
    }
}