最小覆盖子串 · 最短通关小队

怎样从“s="ADOBECODEBANC", t="ABC"：找最短连续窗口，使 A/B/C 各至少出现 1 次（看频次，不看顺序）。”推导出 滑动窗口 · 最小覆盖，并证明每次状态变化都不会漏掉答案？

中心结论：need 债务表 + missing：R 扩到 valid(missing==0)，再缩 L 更新最短；重复字符看数量不看种类。

给定一个源字符串 s，再给一个字符串 T，要求在源字符串中找到一个窗口，这个窗口包含由字符串各种排列组合组成的，窗口中可以包含 T 中没有的字符，如果存在多个，在结果中输出最小的窗口，如果找不到这样的窗口，输出空字符串。

在本站主例中，s="ADOBECODEBANC", t="ABC"：找最短连续窗口，使 A/B/C 各至少出现 1 次（看频次，不看顺序）。

算法最终需要得到或观察：最短子串 "BANC"（顺序 B-A-C）。

枚举所有子串会反复统计大量相同字符；窗口只处理右端新加入和左端刚移出的增量。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“伸缩窗口”，明确答案需要观察什么。
2. 2状态只维护 L/R、窗口串、need 表、missing、bestStart/bestLen。
3. 3转移每一步按照 need 债务表 + missing：R 扩到 valid(missing==0)，再缩 L 更新最短；重复字符看数量不看种类。
4. 4收尾读取 最短子串 "BANC"（顺序 B-A-C）。，并复核边界与复杂度。

右端扩张负责获得新信息，左端收缩负责恢复合法性。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：L/R、窗口串、need 表、missing、bestStart/bestLen。

这一题是滑动窗口的题目，在窗口滑动的过程中不断的包含字符串 T，直到完全包含字符串 T 的字符以后，记下左右窗口的位置和窗口大小。每次都不断更新这个符合条件的窗口和窗口大小的最小值。最后输出结果即可。

need 债务表 + missing：R 扩到 valid(missing==0)，再缩 L 更新最短；重复字符看数量不看种类。

执行过程中持续维护：L/R、窗口串、need 表、missing、bestStart/bestLen。

正确性依赖以下不变量：窗口 valid 当且仅当 missing==0。；need[c]>0 表示仍欠该字符；读到可还债则 missing--。

面试时可以压缩为：变长滑窗：need 记债务，missing 计欠缺实例；R 扩到 missing==0 后缩 L 取最短，移走必要字符则 need>0 且 missing++。O(n)。

落到当前题，执行机制可以压缩为：need 债务表 + missing：R 扩到 valid(missing==0)，再缩 L 更新最短；重复字符看数量不看种类。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入s="ADOBECODEBANC", t="ABC"：找最短连续窗口，使 A/B/C 各至少出现 1 次（看频次，不看顺序）。 因为：need 债务表 + missing：R 扩到 valid(missing==0)，再缩 L 更新最短；重复字符看数量不看种类。
2. 2R=1 · 纳入 b，窗口 abb 在窗口内是全新字符，L 不动，窗口延长到 ab，best=2。 因为：无冲突时只扩张 R 并更新 lastSeen / best。
3. 3R=2 · 纳入 c，窗口 abcc 也是新面孔。连续三字 abc 都合法，best 达到 3。 因为：无冲突时只扩张 R 并更新 lastSeen / best。
4. 4R=5 · 旧 c 在 2，L 跳到 3c 的旧位置 2 >= L=2，L 跳到 3，窗口重新变成 abc。 因为：无冲突时只扩张 R 并更新 lastSeen / best。
5. 5R=7 · 连续两个 b，L 跳到 7b 的旧位置 6 >= L=5，L 直接跳到 7，窗口只剩单个 b。 因为：无冲突时只扩张 R 并更新 lastSeen / best。
6. 6R=10 · 扫描 'A'处理字符 A。 因为：无冲突时只扩张 R 并更新 lastSeen / best。
7. 7R=12 · 扫描 'C'处理字符 C。 因为：旧字符仍在窗口内时必须让 L 跳过它，否则窗口仍含重复。
8. 8收尾与复杂度最短子串 "BANC"（顺序 B-A-C）。 因为：时间 O(n) · 空间 O(σ)。need 债务表 + missing：R 扩到 valid(missing==0)，再缩 L 更新最短；重复字符看数量不看种类。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func minWindow(s string, t string) string {
	if s == "" || t == "" {
		return ""
	}
	var tFreq, sFreq [256]int
	result, left, right, finalLeft, finalRight, minW, count := "", 0, -1, -1, -1, len(s)+1, 0

	for i := 0; i < len(t); i++ {
		tFreq[t[i]-'a']++
	}

	for left < len(s) {
		if right+1 < len(s) && count < len(t) {
			sFreq[s[right+1]-'a']++
			if sFreq[s[right+1]-'a'] <= tFreq[s[right+1]-'a'] {
				count++
			}
			right++
		} else {
			if right-left+1 < minW && count == len(t) {
				minW = right - left + 1
				finalLeft = left
				finalRight = right
			}
			if sFreq[s[left]-'a'] == tFreq[s[left]-'a'] {
				count--
			}
			sFreq[s[left]-'a']--
			left++
		}
	}
	if finalLeft != -1 {
		result = string(s[finalLeft : finalRight+1])
	}
	return result
}

func main() {
    // 1. 主例
    //    输入：mode="longest-unique", text="ADOBECODEBANC"
    //    期望：最短子串 "BANC"（顺序 B-A-C）。
    //
    // 2. 失败 / 未命中
    //    检查：误找连续 "ABC" 或 A→B→C 顺序。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC3 无重复最长（变长滑窗，不变量不同）；LC438 找所有异位词（定长滑窗+频次）
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意s="ADOBECODEBANC", t="ABC"：找最短连续窗口，使 A/B/C 各至少出现 1 次（看频次，不看顺序）。
2. 2重复枚举所有子串会反复统计大量相同字符；窗口只处理右端新加入和左端刚移出的增量。
3. 3优化need 债务表 + missing：R 扩到 valid(missing==0)，再缩 L 更新最短；重复字符看数量不看种类。
4. 4证明窗口 valid 当且仅当 missing==0。；need[c]>0 表示仍欠该字符；读到可还债则 missing--。
5. 5复杂度时间 O(n)，空间 O(σ)