76.最小覆盖子串

发表于： 2023-11-08 分类于： leetcode

字数： 2024 阅读：≈ 5分钟

🏜️ 76.最小覆盖子串

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

思路

基本思想

题目的要求是从s中找到一个子串，子串中的字符可以涵盖s中的字符即可，这样的子串有可能有多个，前提是s的长度要大于等于t的长度，当子串有多个时，就找最小的

利用滑动窗口的思想，经过三步:

不停地扩大滑动窗口的大小（增加右边），直到滑动窗口中的字符子串可以包含t就先停下
不停地缩小滑动窗口的大小（增加左边），直到滑动窗口中的字符子串不能包含t就停下
在第二步的临界点时，也就是下一步就无法包含t时截取一个子串，这个子串就是当前窗口中的最小子串
继续扩大滑动窗口的大小找到下一个合法的窗口，在窗口中找到最小的合法子串

以上步骤中最核心的就是判断当前窗口中的字符子串是否包含t，这里我们预设一个need容器，初始化时key是t中的字符，value是t中每个字符出现的次数，need容器的含义是：当前还需要多少字符才能包含，当当前窗口中的字符子串包含t时，说明不再需要字符，也就是说每一个字符的值都是小于等于0的，在扩大窗口的过程中，每遍历到一个新字符，其需要的字符就会减小一个，字符出现的字数为负代表当前字符是多余的

一旦当前窗口中的字符子串包含t，就需要缩小窗口找到最小的子串，这个临界点就是需要的字符总数为0，所以在遍历的过程中，遇到t中真正出现的字符并且不多于时（当前字符出现的次数大于0），此时这个字符被认为起到良性作用，需要的字符总数可以减一：

1
2
3
4
5
6
char c = s.charAt(index++);
Integer count = need.get(c);
count = count == null ? 0 : count;
if (count > 0) {
    needCount -= 1;
}

例如，当前窗口中的字符为[A,O,D,C],t=“ABC”,那么对于C字符来说，就起到了良性作用，而对于O字符来说，起不到良性作用，get出来的字符出现次数永远小于等于0

当需要的字符总数等于0时，就可以缩小滑动窗口了，需要注意，扩大滑动窗口和缩小滑动窗口的操作不是互斥的，也就是说上一步扩大滑动窗口包含t之后，下一步可以紧接着缩小窗口

执行流程

初始化need容器
遍历s中的每一个字符，减小其需要的数量，当当前字符是真正需要的字符，字符需要总数也减一
当字符需要总数为0时，代表当前滑动窗口中的字符子串可以包含t，此时尝试缩小这个滑动窗口
缩小到临界点时得到了当前的最小子串，尝试保存这个最小子串
遍历结束，得到了最小的子串

图示如下：

以S="DOABECODEBANC"，T="ABC"为例初始状态：

步骤一：不断增加j使滑动窗口增大，直到窗口包含了T的所有元素，need中所有元素的数量都小于等于0，同时needCnt也是0

步骤二：不断增加i使滑动窗口缩小，直到碰到一个必须包含的元素A，此时记录长度更新结果

步骤三：让i再增加一个位置，开始寻找下一个满足条件的滑动窗口

代码

根据以上分析，得出以下代码：

 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
class Solution {
    public String minWindow(String s, String t) {
        String res = "";
        if (s.length() < t.length())
            return res;
        int left = 0, index = 0, needCount = t.length();
        Map<Character, Integer> need = new HashMap<>();
        //统计当前需要多少元素
        for (char c : t.toCharArray()) {
            Integer count = need.get(c);
            count = count == null ? 0 : count;
            need.put(c, count + 1);
        }
        while (index < s.length()) {
            //不在需要字符，说明当前窗口已包含所有t的字符，尝试删除
            if (needCount > 0) {
                char c = s.charAt(index++);
                Integer count = need.get(c);
                count = count == null ? 0 : count;
                if (count > 0) {
                    needCount -= 1;
                }
                need.put(c, count - 1);
            }
            //上一步扩大滑动窗口，下一步可以紧接着缩小滑动窗口
            if (needCount == 0) {
                while (true) {
                    //删除窗口左边的元素
                    char c = s.charAt(left++);
                    Integer count = need.get(c);
                    count = count == null ? 0 : count;
                    need.put(c, count + 1);
                    //一旦出现某个元素需要值为0，说明到了边界
                    //由于移动边界和需要元素的值的数量先变化，所以这里只用变化总数
                    if (count == 0) {
                        //尝试更新最小的子串
                        String temp = s.substring(left - 1, index);
                        if (res.equals(""))
                            res = temp;
                        else
                            res = res.length() > temp.length() ? temp : res;
                        needCount += 1;
                        break;
                    }
                }
            }
        }
        return res;
    }
}

总结

总结来说就是滑动窗口一旦包含t，就尝试缩小滑动窗口，找到当前窗口中的最小能包含t的子串，核心就是如何判断当前子串是否包含t，这里采用了一个need容器，含义是记录当前还需要多少字符才能包含t，初始状态下need的值就是统计t中所有字符出现的次数。

当容器中的字符数量为负时，代表当前字符是多余的，当所有的字符都是负的时候，代表当前窗口中的字符子串可以包含t，重点就是need的更新，新增一个字符进去时，这个字符的需要次数减一，删除一个字符时，这个字符的需要次数加一，在这个基础上，当某一时刻need中的所有元素全为负时就可以包含t，但是为了优化，可以记录一个字符需要总数，当出现一个真正需要的字符（其字符需要的数量还为整数）时，不仅将其need容器中的值减一，字符需要总数的值也减一，当需要总数为0时就说明包含了

缩小滑动窗口的时候，就是依次取出所有的字符，将其需要数量加一，当当前字符的需要数量大于0时，说明已经不能再包含t了，也就是到达了临界点，此时就找到了当前滑动窗口中的最小子串，尝试记录全局出现的最小子串返回就是最终的结果