LeetCode 76. 最小覆盖子串
题目描述
题意分析
在
s中找一个最短的连续子串，使t中每个字符在子串里的出现次数都不少于它在t中的次数。覆盖只关心字符和数量，不要求出现顺序与t一致，也允许包含额外字符。返回的是子串本身；不存在覆盖时返回空串，存在时题目保证最短答案唯一。两个字符串都非空，只包含大小写英文字母，大小写需要区分；重复字符必须逐个满足，不能只检查字符种类。
解法：滑动窗口维护字符欠账
核心思路
[!blue]
固定左端后，向右扩张只会增加字符，不会让已经满足的需求失效；固定右端后，缩短左侧才可能得到更短答案。这种单向变化适合滑动窗口：缺字符时扩张，覆盖后收缩。
对当前窗口
[left, right]，定义need[c] = t 中 c 的数量 - 窗口中 c 的数量。正数表示还缺，零表示刚好够，负数表示多余。再用missing记录所有正欠账之和，也就是还缺多少个字符；初始窗口为空，所以missing = t.length()。字符
in入窗时，总要执行need[in]--。只有入窗前need[in] > 0，它才补上一个缺口，missing才减一；本来就够用的字符继续增加，不会抵消其他字符的欠账。因此missing == 0恰好表示窗口覆盖了全部需求。窗口覆盖后，先记录答案，再尝试移出左端字符。移出
out时先执行need[out]++；若增加后为正，说明刚移走的是必需字符，missing加一，窗口重新缺失，必须停止收缩。否则移走的只是多余字符，可以继续缩短。左指针不需要回退：每个被移走的左端点，都已经和当时的右端点组成过合法窗口并参与答案比较；以后右端点更靠右，以同一个左端点组成的窗口只会更长。持续扩张和收缩即可找到最短答案，同时两个指针都只遍历
s一次。
解题步骤
- 统计
t的字符频次作为初始need，令missing = t.length()、left = 0。用bestStart保存答案起点，bestLen = s.length() + 1表示尚未找到答案。- 右指针逐个加入字符：先依据旧的
need[in]判断是否减少missing，再将need[in]减一。- 当
missing == 0时，用当前长度right - left + 1更新最短答案，然后移出左端字符、右移left，恢复欠账并判断是否重新缺失。- 重复第 3 步直到窗口不再覆盖，再继续扩张右端。扫描结束后，若
bestLen仍大于s.length()则返回空串，否则截取保存的区间。
代码实现
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;
int bestStart = 0;
int 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)$。统计
t扫描一次，窗口中每个字符最多进入一次、离开一次；内层收缩的总次数不超过s的长度，因此不是平方复杂度。- 空间复杂度：$O(1)$，不计返回结果。题目字符仅为大小写英文字母，长度为 128 的数组足以按字符编码直接计数，数组大小不随输入增长。
关键点总结
[!green]
missing统计缺少的字符总数，重复字符也要分别计数。- 入窗时先判断旧的
need，出窗时先增加need再判断。need的负值表示多余字符，不影响窗口合法性。- 答案只在窗口合法、移出左端之前更新；用
while持续收缩才能去掉全部可删除前缀。
易错点总结
[!yellow]
- 只统计字符种类而忽略出现次数，会错误处理
t中的重复字符。- 入窗时先减少
need再判断，会漏掉刚好补齐的字符。- 收缩只执行一次而不是持续执行，会留下可删除的前缀。
- 若把
bestLen初值设为s.length()，当前返回判断将无法区分从未找到覆盖与整串恰好为答案，可能在无解时错误返回原串。- 题目包含大小写字母，不能使用长度 26 且按
c - 'a'索引的数组。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 209. 长度最小的子数组 | 中等 | 同样求满足约束的最短窗口，本题的约束是字符多重集合覆盖，原题是正数总和。 |
| 567. 字符串的排列 | 中等 | 原题要求固定长度与精确频次，本题允许额外字符并尽量缩短覆盖窗口。 |
| 438. 找到字符串中所有字母异位词 | 中等 | 用字符需求计数判断窗口是否覆盖目标；本题收缩窗口寻找最短覆盖，该题固定长度后记录所有异位词起点。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！