线性动态规划：最小覆盖子串（Minimum Window Substring）

题目描述

给定两个字符串 s 和 t，返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。

注意：

• 对于 t 中重复的字符，在子串中该字符的数量必须不少于 t 中该字符的数量。
• 如果存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3：

输入：s = "a", t = "aa"
输出：""
解释：t 中有两个 'a'，但 s 中只有一个 'a'，所以无法涵盖。

解题思路

这个问题是经典的滑动窗口（双指针）与哈希表结合的问题，但也可以通过动态规划的思路来理解其状态转移。核心思想是维护一个滑动窗口，通过移动左右指针来动态调整窗口大小，确保窗口内包含 t 的所有字符且尽可能短。

主要步骤：

1. 统计 t 中每个字符出现的次数，用哈希表 need 记录。
2. 使用滑动窗口，用哈希表 window 记录窗口中字符的出现次数。
3. 移动右指针扩大窗口，直到窗口内包含了 t 的所有字符。
4. 然后移动左指针缩小窗口，同时更新最小子串的起始位置和长度。
5. 重复步骤 3-4 直到右指针遍历完整个字符串。

动态规划视角：
实际上，窗口的扩展和收缩可以看作是在维护一个状态：当前窗口是否满足条件。但这个问题更自然的解法是滑动窗口，动态规划通常用于序列匹配或子串计数，而不直接用于找最小窗口。

注意：虽然题目常被归类为滑动窗口，但我们可以用动态规划的思想来优化匹配判断，比如用“已满足的字符种类数”来避免每次遍历 need 检查是否满足条件。

详细解题步骤

步骤 1：初始化

• 统计 t 中字符的出现频率，存入字典 need。need[c] 表示字符 c 还需要多少才能满足 t 的要求。
• 初始化 window 字典，用于记录当前窗口中字符的出现次数。
• 定义变量：
  • valid：记录当前窗口中已满足 need 条件的字符种类数（即 window[c] >= need[c] 的字符数）。
  • start 和 min_len：记录最小覆盖子串的起始位置和长度。
  • 左右指针 left 和 right，初始都指向 s 的开头。

步骤 2：滑动窗口扩展

• 右指针 right 从 0 开始，逐步向右移动，每次将 s[right] 加入窗口：
  • 如果 s[right] 是 t 中的字符，则 window[s[right]] 增加 1。
  • 如果 window[s[right]] 恰好等于 need[s[right]]，说明这个字符的数量已满足要求，valid 加 1。
• 当 valid 等于 need 的大小（即 t 中不同字符的种类数）时，说明当前窗口已包含 t 的所有字符。

步骤 3：滑动窗口收缩

• 在窗口满足条件时，尝试移动左指针 left 收缩窗口，以寻找更小的子串：
  • 如果当前窗口长度 right - left + 1 小于 min_len，更新 min_len 和 start。
  • 如果 s[left] 是 t 中的字符，则减少 window[s[left]]，如果减少后 window[s[left]] < need[s[left]]，则 valid 减 1（因为该字符不再满足条件）。
  • 移动 left 指针向右一步。
• 重复收缩直到窗口不再满足条件（valid < need 的大小）。

步骤 4：重复扩展和收缩

• 继续移动右指针，重复步骤 2 和 3，直到 right 遍历完 s。

步骤 5：返回结果

• 如果 min_len 仍是初始值（比如设为无穷大），则返回空字符串，否则返回 s[start:start+min_len]。

举例说明

以 s = "ADOBECODEBANC", t = "ABC" 为例：

1. need = {'A':1, 'B':1, 'C':1}，valid=0，min_len=∞。
2. 右指针移动：
   • 窗口 "A" → valid=1（A 满足）。
   • 窗口 "ADOBE" → 加入 B 时 valid=2，加入 C 时 valid=3，此时窗口 "ADOBEC" 包含所有字符，长度 6。
3. 收缩左指针：
   • 移出 A 后，A 不满足条件，valid=2，窗口变为 "DOBEC"。
4. 继续右移指针，直到再次满足条件（如窗口 "DOBECODEBA" 加入 B 和 A 后 valid 重新为 3），收缩得到 "BANC"，长度 4 更小。
5. 最终得到 "BANC"。

复杂度分析

• 时间复杂度：O(|s| + |t|)，左右指针各遍历一次。
• 空间复杂度：O(字符集大小)，主要是 need 和 window 字典。

关键点

1. 用 valid 变量避免每次检查整个 need，这是优化核心。
2. 滑动窗口扩展是为了满足条件，收缩是为了优化最小长度。
3. 窗口内可能包含多余字符（如示例中的 D、O 等），只要满足 t 的字符要求即可。

思考拓展

• 如果要求时间复杂度更优（比如 O(n)），上述方法已是最优。
• 如果 s 和 t 包含 Unicode 字符，可以用字典处理。
• 类似问题：找到包含 t 所有字符的最长子串、统计所有覆盖子串等。

希望这个讲解能帮助你理解最小覆盖子串问题的解法！