Leetcode 76.最小覆盖子串

题目描述：

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

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

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

示例 1：

1
2

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

示例 2：

1
2

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

提示：

• $1 <= s.length, t.length <= 10^5$
• s 和 t 由英文字母组成

链接：

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

题目分析

  通过观察示例我们可以得知，覆盖 t 并不需要按照顺序，也即 s 的某个子串中只需要包含 t 中的所有字母即可。并且 t 中的字母是可以重复的，比如有两个 'a'，则符合条件的 s 子串也必须包含至少两个 'a'。那么我们可以考虑使用一个哈希表来记录 t 中的所有字母以及它们的个数，作为 s 子串需要满足的 target。
  而对于子串的问题，我们可以使用滑动窗口的思想，使用 left 和 right 两个变量记录窗口的边界，并且维护另一个哈希表 now，记录当前子串中各字符的个数，使用一个布尔变量 flag 表示 now 是否能覆盖 target。如果能够覆盖，则 left 右移，缩小窗口；如果不能覆盖，则 right 右移，扩大窗口。这样动态地维护窗口并且记录能够覆盖的最小长度，记录为答案。
  需要注意的地方有以下几点。

• s 的长度小于 t 的长度时，肯定无法覆盖 t，可以直接返回空串。
• left 和 right 都是从 0 开始的，其中 left 处于窗口内，right 处于窗口外，也即子串为 s[left ~ right-1]，长度刚好为 right-left。
• 即使 right 到了终点，也仍然存在 left 继续右移缩小窗口的可能，因此退出循环条件还必须是子串已经无法覆盖 target（也即 flag 变为 false）。
• 当 left 右移时（此时 flag 为 true），无需对右移后的整个哈希表进行判断，因为改变的只有 s[left]，还能不能覆盖只取决于 s[left] 的数目会不会因此而变得不足。（实际上，如果维护的是能够满足覆盖的字母种类，right 右移时也可以只检查新添字母之后，该字母数目的增加能否使得满足覆盖的字母种类已经达到了 t 的字母种类。）
• minlength 记录了最小子串长度，初始值赋为 INT_MAX，如果到最后这个值仍然没有被修改，则说明不存在能够覆盖 t 的子串，按照题目要求返回空串。

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

class Solution {
    bool check(unordered_map<char, int>& target, unordered_map<char, int>& now){
        for(auto it = target.begin(); it != target.end(); it++){
            if(now[it->first] < it->second){
                return false;
            }
        }
        return true;
    }
public:
    string minWindow(string s, string t) {
        if(s.size() < t.size()) return "";

        unordered_map<char, int> target, now;

        for(int i = 0; i < t.size(); i++){
            target[t[i]]++;
        }

        int left = 0, right = 0;
        int resleft, minlength = INT_MAX;
        bool flag = false;
        while(flag || right < s.size()){
            if(flag){
                if(right - left < minlength){
                    resleft = left;
                    minlength = right - left;
                }
                now[s[left]]--;
                if(now[s[left]] < target[s[left]]){
                    flag = false;
                }
                left++;
            }
            else{
                now[s[right]]++;
                flag = check(target, now);
                right++;
            }
        }

        return minlength == INT_MAX ? "" : s.substr(resleft, minlength);
    }
};

  时间复杂度：$O(\alpha|s|+|t|)$，其中 $\alpha、s、t$ 分别是字符集的大小、字符串 s 和 t。t 的字符要加入哈希表中，而最坏情况下，s 的所有字符都需要加入哈希表一次、从哈希表删除一次，并且每次加入都需要遍历一次 target 检查是否满足覆盖，而 target 的大小也即字符集的大小。
  空间复杂度：$O(\alpha)$，其中 $\alpha$ 是字符集的大小。也即两张哈希表的空间开销。