hot 100 第十二题 12.最小覆盖子串

题目：

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

测试用例保证答案唯一。

示例 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 的所有字符” 不是指包含 t 本身，而是指：

• t 中每种字符都出现
• 出现次数不少于 t 中的次数

<span style="color:#eaecf0"><code>t = "AAB"

"AABB" ✓ (A出现2次≥2, B出现2次≥1)
"ABA" ✓ (A出现2次≥2, B出现1次≥1)
"AB" ✗ (A只出现1次<2)</code></span>

窗口的两个动作

想象你拿着一个可伸缩的尺子在字符串上滑动：

<span style="color:#eaecf0"><code>s = "ADOBECODEBANC", t = "ABC"

1. 右边界不断扩展，直到包含 ABC:
A → AD → ADO → ADOB → ADOBE → ADOBEC ✓ 包含了！
^^^^^^

2. 左边界收缩，尽可能缩短但仍要包含 ABC:
ADOBEC → DOBEC ✗ (没有A了，停止)

3. 右边界继续扩展找下一个:
DOBEC → DOBECO → DOBECOD → … → DOBECODEBA ✓

4. 左边界收缩:
DOBECODEBA → OBECODEBA → … → BANC ✓
^^^^
这是最短的！</code></span>

如何判断"包含"？

用两个计数数组：

<span style="color:#eaecf0"><code>tCount: 记录 t 中每个字符需要的数量
windowCount: 记录当前窗口中每个字符的数量

t = "ABC"
tCount: A=1, B=1, C=1

窗口 "ADOBEC":
windowCount: A=1, D=1, O=1, B=1, E=1, C=1

比较:
A: windowCount[A]=1 ≥ tCount[A]=1 ✓
B: windowCount[B]=1 ≥ tCount[B]=1 ✓
C: windowCount[C]=1 ≥ tCount[C]=1 ✓
→ 包含了！</code></span>

优化：用 matched 计数

不需要每次遍历比较，而是用一个变量 记录"已经满足的字符种类数"：matched

<span style="color:#eaecf0"><code>t = "ABC" → required = 3 (需要匹配3种字符)

窗口加入 A: windowCount[A]=1 达到要求 → matched=1
窗口加入 B: windowCount[B]=1 达到要求 → matched=2
窗口加入 C: windowCount[C]=1 达到要求 → matched=3

matched == required → 包含了！</code></span>

完整流程图解

<span style="color:#eaecf0"><code>s = "ADOBECODEBANC", t = "ABC"

右指针扩展阶段:
A D O B E C
→ → → → → → matched 变化: 1→1→1→2→2→3 ✓

左指针收缩阶段:
A D O B E C
← matched 还是 3 吗？移除 A 后变成 2 ✗ 停止

右指针继续:
D O B E C O D E B A
→ → → → → → → → → matched 变化: 2→2→2→2→2→2→3 ✓

左指针收缩:
D O B E C O D E B A
← ← ← 移除 D, O, B 后 matched 还是 3
移除第一个 E 后 matched 还是 3
移除 C 后 matched 变成 2 ✗ 停止

继续右移找到:
B A N C
← ← ← ← 这是最短的！长度=4</code></span>

双指针的协作

<span style="color:#eaecf0"><code>右指针职责: 扩展窗口，让窗口"够格"(包含所有字符)
左指针职责: 收缩窗口，让窗口"最优"(尽可能短)

右指针走完整个字符串，左指针跟着调整
每个字符最多被访问2次(进入窗口1次，离开窗口1次)
→ 时间复杂度 O(n)</code></span>

本质

这是**尺取法（Two Pointers）**的典型应用：

• 维护一个动态窗口
• 右边界负责"达标"（满足条件）
• 左边界负责"最优"（最小化结果）
• 两个指针配合，遍历所有可能的合法窗口

类似题目都可以用这个套路：找最长/最短的满足某条件的子串/子数组。

题解：

class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";

// 统计 t 中每个字符的出现次数
int[] tCount = new int[128]; // ASCII 字符集
for (char c : t.toCharArray()) {
tCount[c]++;
}

// 窗口内字符计数
int[] windowCount = new int[128];

int left = 0, right = 0;
int minLen = Integer.MAX_VALUE;
int minStart = 0;
int matched = 0; // 已匹配的字符种类数
int required = 0; // t 中不同字符的种类数

// 计算 t 中有多少种不同字符
for (int count : tCount) {
if (count > 0) required++;
}

while (right < s.length()) {
// 扩展右边界
char rightChar = s.charAt(right);
windowCount[rightChar]++;

// 如果当前字符的数量刚好满足要求，matched++
if (tCount[rightChar] > 0 && windowCount[rightChar] == tCount[rightChar]) {
matched++;
}

// 收缩左边界
while (matched == required) {
// 更新最小窗口
if (right – left + 1 < minLen) {
minLen = right – left + 1;
minStart = left;
}

// 移除左边界字符
char leftChar = s.charAt(left);
windowCount[leftChar]–;

// 如果移除后不再满足要求，matched–
if (tCount[leftChar] > 0 && windowCount[leftChar] < tCount[leftChar]) {
matched–;
}

left++;
}

right++;
}

return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}
}