76. 最小覆盖子串

题目

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

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”
示例 2：

输入：s = “a”, t = “a”
输出：”a”
示例 3:

输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

思路

滑动窗口实现，两个指针：left和right，最开始right向右移动直到目标字符串被全部包括，然后right想右移动在遇到目标字符串重复字符的时候，left判断是否可以右移，记录当前字符最小长度，一直到right移动到末尾。

难点：判断当前字符串是否包含目标字符串

  1. 写一个方法，方法使用双重for循环判断是否全部包含目标字符串
  2. 使用一个hashmap或者一个字符数组存放已有字符串指定字符的出现次数和目标字符串自定字符的出现次数

本题中使用一个字符数组存放需要的字符和已经存放的字符的出现次数，在使用这种方法的时候，我们无法拿到字符在原字符串中出现的索引位置，也就是无法判断预见相同字符的时候，left是否可以右移（无法知道这个字符是在做左边还是在中间，还是在其他位置，出现非左边的时候我们是无法移动的）

所以我们可以换一个思路，每次遇到重复字符的时候我们强制移除之前的字符的位置，然后left++，再次重新尝试包含所以字符

实现

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
private static class Solution {
    public String minWindow(String s, String t) {

        if (s == null || "".equals(s) || t == null || "".equals(t) || s.length() < t.length()) {
            return "";
        }

        int[] need = new int[128];
        int[] have = new int[128];

        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        int left = 0, right = 0, min = s.length() + 1, count = 0, start = 0;

        while (right < s.length()) {
            char r = s.charAt(right);
            // 不需要统计
            if (need[r] == 0) {
                right++;
                continue;
            }
            // 需要统计，但是还没有全部包含,这个时候才需要count++
            if (have[r] < need[r]) {
                count++;
            }
            have[r]++;
            right++;
            // 已经全部包含目标函数了
            while (count == t.length()) {
                if (right - left < min) {
                    min = right - left;
                    start = left;
                }

                char l = s.charAt(left);
                // 不需要这字符，可以直接减去
                if (need[l] == 0) {
                    left++;
                    continue;
                }
                // 如果遇到相同的字符，强制移除之前的字符，left指针右移
                if (have[l] == need[l]) {
                    count--;
                }
                have[l]--;
                left++;

            }
        }
        if (min == s.length() + 1) {
            return "";
        }
        return s.substring(start, start + min);
    }
}