76. 最小覆盖子串

题意

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

在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

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

难度

困难

示例

示例 1：

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

输出："BANC"

解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

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

输出："a"

解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"

输出: ""

解释: t 中两个字符 'a' 均应包含在 s 的子串中，

因此没有符合条件的子字符串，返回空字符串。

分析

本题最暴力的方法，显然是枚举每一个串，然后去检验是否和 t 中的字符数量一致。

但是这样子的时间复杂度——$ O(n^2) $，远远超出了我们的承受范围。

所以我们要考虑别的算法——滑动窗口，正好我们要维持的条件是——窗口内的字符数量

和 t 中的字符数量一致。

首先，用一个 bucket1 来记录 t 中的字符数量。

这时候我们就能够使用两个变量 lef、rig 来表示窗口的左端点和右端点，先让右端点 rig

延申，记录右端点延申的时候经过的每个字符，并且用一个 bucket2 来统计相应的字符

数量，直到 bucket2 中的字符数量均大于等于 bucket1。

这时候，我们就找到一个可行解了，接下来的步骤就是优化这个可行解——向后移动左端

点 lef。

现在，我们让左端点向右移动，并且将移动时经历过的字符，从 bucket2 中删去相应的

数量，保持 bucket2 始终能够表示我们窗口内的字符数量，这时候的区间长度正在减

小，是的，我们正在不断求最优解！

可能有些同学算不清楚此时的时间复杂度，但其实有个非常容易观察出来的方法：观察

lef 和 rig 的移动次数，因为二者最多分别遍历整个字符串一次，所以时间复杂度为$ O(n)

$！。

class Solution {

public String minWindow(String s, String t) {

StringBuilder res = new StringBuilder();

HashMap<Character,Integer> bucket1 = new HashMap<>();

HashMap<Character,Integer> bucket2 = new HashMap<>();

for(int i = 0;i < t.length();i++)

bucket1.put(t.charAt(i),bucket1.getOrDefault(t.charAt(i),0) + 1);

int lef = 0,rig = 0;

int num = 0;

int ansLength = s.length() + 1;

int ansLef = 0,ansRig = 0;

while(rig < s.length()){

char nowPos = s.charAt(rig);

rig++;

if(bucket1.getOrDefault(nowPos,0) != 0){

bucket2.put(nowPos,bucket2.getOrDefault(nowPos,0) + 1);

if(bucket2.get(nowPos).equals(bucket1.get(nowPos)))

num++;

}

while(num == bucket1.size()){

if(rig - lef < ansLength){

ansLef = lef;

ansRig = rig;

ansLength = rig - lef;

}

char pushPos = s.charAt(lef);

lef++;

if(bucket1.containsKey(pushPos)){

bucket2.put(pushPos,bucket2.get(pushPos) - 1);

if(bucket2.get(pushPos) < bucket1.get(pushPos)){

num--;

}

}

}

}

if(ansLength == s.length() + 1)

return res.toString();

for(int i = ansLef;i < ansRig;i++)

res.append(s.charAt(i));

 return res.toString();

}

}

1677747504672-37e48da1-f1f8-44d8-a670-89332ae22fc9.png

总结

滑动窗口通常用于求解连续区间满足一定条件下的区间长度的最小值，非常适合这种题

目，所以当我们看到此类题目时，就要下意识地想到滑动窗口。

力扣链接：https://leetcode.cn/problems/minimum-window-substring/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启

动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道

LeetCode 经典题。

PDF 版本目前只针对二哥编程星球的球友开放，如果你也想一起打卡学习算法的话，戳链

接加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球（目前已有 1800 多名球友

加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

更新: 2023-03-02 08:58:27

原文: https://www.yuque.com/itwanger/czfoq9/acs74o