LeetCode LCR 017. 最小覆盖子串
题目描述
题意分析
在
s中寻找长度最短的连续子串，使它包含t的全部字符及所需出现次数，返回该子串本身。目标中某个字符出现多次，窗口里也必须至少有相同数量；窗口可以包含额外字符，也不要求字符顺序与t相同。不存在满足条件的窗口时返回空字符串；有多个同样短的答案时返回任意一个即可。两串包含大小写英文字母，大小写分别计数。题目保证目标非空，因此合法覆盖窗口也不会是空区间。
解法：滑动窗口维护字符欠账
核心思路
[!blue]
用
[left, right]表示窗口。目标字符不足时只能扩大范围寻找缺少的字符；已经覆盖时，则尝试从左侧移走多余部分，让结果更短。需要把“是否覆盖”维护成常数时间可检查的状态。定义
need[ch] = 目标需求次数 - 当前窗口次数。正数表示还缺，零表示刚好足够，负数表示多余；即使不是目标字符，也照常在入窗时减一、出窗时加一。再用missing保存所有正数缺口之和，初始为t.length()，因此missing == 0恰好等价于窗口已经覆盖全部需求。字符入窗前，如果它的
need仍为正，说明这次补上了一个缺口，先令missing--，再减少need。如果原来已经够用，多一个副本只会增加富余，不改变缺口总数。出窗时则先恢复need，恢复后若为正，说明刚移走的是必需副本，令missing++。这两个判断分别针对旧缺口与新缺口，顺序不能互换。每扩张一次右端，只要
missing == 0就连续收缩：先记录当前合法窗口的长度和起点，再移走左端字符。左侧的无关字符或富余副本可以继续移除；直到移走一个必需字符、窗口重新不满足覆盖时才停止。为什么左端无需回退？一个旧左端只有在其窗口已经合法并记录过之后才会被移走。未来再把右端延长，用同一个旧左端只能得到更长的窗口，不可能改善已经记录的结果。因此可以永久跳过这些左端，把搜索集中在尚可能更短的区间。
全程只保存最短长度与起点，结束后再截取一次结果，避免每次改进答案都复制子串。最短长度初始化为不可能出现的上界，它保持不变就表示从未形成合法窗口。
解题步骤
- 统计目标字符频次到
need，令missing = t.length()、left = 0，最优长度取不可达上界。- 右端加入字符前，若其需求仍为正就减少总缺口；然后减少该字符的
need。- 当总缺口为零时，先用当前窗口更新最优长度和起点。
- 移走左端字符，恢复对应
need；恢复后若为正，则总缺口加一。随后左端右移，继续判断是否还能收缩。- 扫描结束后，若最优长度未更新则返回空串，否则截取
[bestStart, bestStart + bestLen)。
代码实现
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 = Integer.MAX_VALUE;
for (int right = 0; right < s.length(); right++) {
char in = s.charAt(right);
if (need[in] > 0) {
missing--;
}
need[in]--;
// missing 为 0 时窗口已覆盖 t，开始尽量左收缩。
while (missing == 0) {
int len = right - left + 1;
if (len < bestLen) {
bestLen = len;
bestStart = left;
}
char out = s.charAt(left);
need[out]++;
if (need[out] > 0) {
missing++;
}
left++;
}
}
if (bestLen == Integer.MAX_VALUE) {
return "";
}
return 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 := 0
bestStart := 0
bestLen := len(s) + 1
for right := 0; right < len(s); right++ {
in := s[right]
if need[in] > 0 {
missing--
}
need[in]--
// missing 为 0 时窗口已覆盖 t，开始尽量左收缩。
for missing == 0 {
length := right - left + 1
if length < bestLen {
bestLen = length
bestStart = left
}
out := s[left]
need[out]++
if need[out] > 0 {
missing++
}
left++
}
}
if bestLen == len(s)+1 {
return ""
}
return s[bestStart : bestStart+bestLen]
}
复杂度分析
- 时间复杂度：
O(|s| + |t|)。目标统计一次，右端加入每个位置一次，左端移出每个位置至多一次，覆盖判断只检查一个总缺口变量。- 空间复杂度：不计返回值为
O(1)。计数数组固定为128项，能够容纳题目中的大小写英文字母。
关键点总结
[!green]
- 覆盖按出现次数判断，
missing是缺少字符的总个数，不是缺少的种类数。- 负的
need记录富余量，帮助区分移走的是多余字符还是必需字符。- 窗口合法时先记录再收缩，旧左端记录过更短候选后就不必回退。
- 起点、长度和无解标记必须配套，最终只截取一次字符串。
易错点总结
[!yellow]
- 入窗先减需求，再用
> 0判断旧缺口：填补最后一个缺口时会漏减missing。- 把
need == 0也当成仍有缺口：多余字符会错误降低总缺口，导致未覆盖的窗口被误认为合法。- 不允许需求变负：会丢失富余次数，出窗时无法判断是否真正破坏覆盖。
- 收缩后才记录当前答案：可能记录已经移走必需字符的非法窗口。
- 只收缩一次：左侧可能有多个可移出的字符，需要持续尝试直到覆盖失效。
- 字符种类足够就认为覆盖：重复字符的次数仍必须满足需求。
- 把长度当作截取结束下标：右端应为
bestStart + bestLen，不是单独的bestLen。- 仅修改长度初值、不修改无解判断：会把从未覆盖的区间误当成答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 209. 长度最小的子数组 | 中等 | 同样求满足约束的最短窗口，本题的约束是字符多重集合覆盖，原题是正数总和。 |
| 567. 字符串的排列 | 中等 | 原题要求固定长度与精确频次，本题允许额外字符并尽量缩短覆盖窗口。 |