LeetCode 76. 最小覆盖子串
目录
题目描述
题意分析
在
s中找一段连续的子串，使它「覆盖」t，并且长度最短；若不存在这样的子串就返回空字符串。答案要的是子串本身，所以除了长度还得记住起点。「覆盖」的判定标准是按重数而不是按种类：
t中某个字符出现k次，窗口里就必须出现至少k次，多出来不要紧。这是本题最容易读错的一处——t = "AABC"时只含一个A的窗口不算覆盖。「连续」意味着答案对应原串上的一个区间
[left, right]，可以用两个下标刻画，而不必枚举字符组合。更重要的是覆盖性对区间单调：若[left, right]已经覆盖t，那么把右端点继续往右扩张仍然覆盖；反之若当前区间没覆盖，缩短它只会更差。这条单调性说明左右端点都只需要单向移动。另一个可以利用的信号是字符集有限：题面给的是英文字母大小写，全部落在 ASCII 范围内，因此计数容器可以用一个固定长度的数组，判断是否覆盖不需要遍历哈希表。
边界情形：
t比s长时必然返回空串；s中根本没有某个必需字符时返回空串；答案可能就是整个s（如s = "ab"、t = "ba"），所以最优长度的初值必须比s的长度还大；s与t都只有一个字符且相等时答案是长度 1 的窗口，收缩逻辑不能把长度 1 的窗口排除掉。
解法：滑动窗口维护字符欠账
核心思路
用
need[c]表示窗口还需要多少个字符c，missing表示总共还缺多少个字符。字符进入窗口时减少欠账，字符离开窗口时恢复欠账；missing == 0表示当前窗口已覆盖t。右指针负责扩张窗口。当窗口合法时，持续右移左指针并更新最短答案，直到窗口再次缺少字符。
need[c]可以为负数，表示该字符在窗口中有剩余。
解题步骤
- 统计
t中每个字符的需求，并令missing = t.length()。- 右指针遍历
s：若进入的字符仍有需求，先减少missing，再减少其need。- 当
missing == 0时，记录更短的窗口。- 移出左端字符并增加其
need；若增加后为正，说明窗口重新缺少该字符，增加missing。- 遍历结束后返回记录的最短子串；从未出现合法窗口则返回空串。
代码实现
class Solution {
public String minWindow(String s, String t) {
int[] need = new int[128];
for (int i = 0; i < t.length(); i++) {
need[t.charAt(i)]++;
}
int missing = t.length();
int left = 0, bestStart = 0, bestLen = s.length() + 1;
for (int right = 0; right < s.length(); right++) {
char in = s.charAt(right);
if (need[in] > 0) {
missing--;
}
need[in]--;
while (missing == 0) {
int len = right - left + 1;
if (len < bestLen) {
bestStart = left;
bestLen = len;
}
char out = s.charAt(left++);
need[out]++;
if (need[out] > 0) {
missing++;
}
}
}
return bestLen > s.length()
? ""
: s.substring(bestStart, bestStart + bestLen);
}
}
func minWindow(s string, t string) string {
need := make([]int, 128)
for i := 0; i < len(t); i++ {
need[t[i]]++
}
missing := len(t)
left, bestStart, bestLen := 0, 0, len(s)+1
for right := 0; right < len(s); right++ {
in := s[right]
if need[in] > 0 {
missing--
}
need[in]--
for missing == 0 {
length := right - left + 1
if length < bestLen {
bestStart, bestLen = left, length
}
out := s[left]
left++
need[out]++
if need[out] > 0 {
missing++
}
}
}
if bestLen > len(s) {
return ""
}
return s[bestStart : bestStart+bestLen]
}
复杂度分析
- 时间复杂度：$O(\lvert s\rvert + \lvert t\rvert)$，左右指针都只向右移动。
- 空间复杂度：$O(C)$，
C = 128为题目限定的 ASCII 字符集大小，可视为常数空间。
关键点总结
missing统计缺少的字符总数，重复字符也要分别计数。- 入窗时先判断旧的
need，出窗时先增加need再判断。need的负值表示多余字符，不影响窗口合法性。- 合法窗口必须用
while持续收缩，才能得到当前右端点下的最短窗口。
易错点总结
- 只统计字符种类而忽略出现次数，会错误处理
t中的重复字符。- 入窗时先减少
need再判断，会漏掉刚好补齐的字符。- 收缩只执行一次而不是持续执行，会留下可删除的前缀。
- 答案长度初值若设为
s.length()，会漏掉答案恰好是整个s的情况。- 题目包含大小写字母，不能使用长度 26 且按
c - 'a'索引的数组。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 017. 最小覆盖子串 | 困难 | 与本题同题异名，代码可直接照搬 |
| 面试题 17.18. 最短超串 | 中等 | 对象是整数数组且待覆盖元素互不重复，返回下标区间而非子串 |
| 3. 无重复字符的最长子串 | 中等 | 求最长而非最短，约束是「窗口内不重复」，扩张与收缩的触发条件正好相反 |
| 209. 长度最小的子数组 | 中等 | 同样求最短窗口，但合法性判据是数值和 ≥ target，只需一个前缀和变量 |
| 438. 找到字符串中所有字母异位词 | 中等 | 窗口长度固定为模式串长度，要求恰好相等而非覆盖，收缩退化为定长滑动 |
| 567. 字符串的排列 | 中等 | 定长窗口的判定版，只需返回是否存在，找到一个即可提前退出 |
| 30. 串联所有单词的子串 | 困难 | 覆盖单位从字符变成等长单词，需要按单词长度分组做多条独立的滑动窗口 |
| 424. 替换后的最长重复字符 | 中等 | 合法条件变成「窗口长度减最高频次 ≤ k」，需要额外维护窗口内的众数频次 |
| 1004. 最大连续1的个数 III | 中等 | 只对 0 计数，欠账表退化成一个整数，是本题写法的最简特例 |
| 727. 最小窗口子序列 | 困难 | 要求 t 按顺序作为子序列出现，覆盖性不再对区间单调，滑动窗口整体失效 |