好的，我们这次来详细讲解 LeetCode 第 76 题：「最小覆盖子串」。

这道题是滑动窗口领域的经典难题，综合了哈希表、双指针和滑动窗口等多种技巧，理解它对你掌握复杂的字符串处理非常有帮助。

第一步：理解题目描述

题目

给你一个字符串 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'，所以不存在符合条件的子串。

第二步：分析问题与核心思路

我们的目标是：在 s 中找到一个长度最小的连续子串，使得这个子串包含 t 中的所有字符（包括重复字符）。

关键点分析：

1. 子串是连续的：这提示我们可以使用滑动窗口技巧。滑动窗口能在 O(n) 时间内遍历所有可能的连续子串。
2. 需要包含 t 的所有字符：这意味着我们需要一种快速的方法来判断当前窗口是否“满足条件”。
3. 字符数量要匹配：对于 t 中出现多次的字符（如 "aa"），窗口内该字符的数量不能少于 t 中的数量。

核心思路：滑动窗口 + 哈希表（字典）

1. 使用两个哈希表（字典）：

   • need：记录 t 中每个字符需要的数量。例如，t = "AABC"，则 need['A'] = 2, need['B'] = 1, need['C'] = 1。
   • window：记录当前滑动窗口内各个字符的实际数量。

2. 使用双指针维护一个滑动窗口：

   • left 和 right 指针初始都在 s 的最左侧（索引 0）。
   • 我们不断移动右指针 right 来扩大窗口，直到窗口包含了 t 的所有字符。
   • 然后，我们移动左指针 left 来收缩窗口，在保证窗口仍然包含 t 所有字符的前提下，尝试找到更小的满足条件的子串。

3. 如何判断窗口是否“满足条件”？

   • 我们引入一个关键变量 valid。
   • 对于 t 中的每个字符 c，只有当 window[c]（窗口中的数量）大于等于 need[c]（需要的数量）时，我们才认为字符 c 的条件被满足了。
   • 当所有在 need 中的字符（即 t 中的字符）的条件都被满足时，valid 的值就等于 need 中不同字符的个数。此时，当前窗口就是一个可行的解。

第三步：详细步骤拆解（以示例1为例）

s = "ADOBECODEBANC", t = "ABC"

1. 初始化：

   • need = {'A':1, 'B':1, 'C':1}
   • window = {'A':0, 'B':0, 'C':0} (初始为0)
   • left = 0, right = 0
   • valid = 0 (当前满足条件的字符数为0)
   • start = 0, len_sub = 无穷大 (用于记录最终结果子串的起始位置和长度)

2. 步骤一：扩大窗口（移动 right）

   • right 指向 'A'：window['A'] 变为 1。window['A'] (1) == need['A'] (1)，所以 valid 加 1，变为 1。
   • right 指向 'D'：'D' 不在 t 中，忽略。
   • right 指向 'O'：忽略。
   • right 指向 'B'：window['B'] 变为 1。window['B'] (1) == need['B'] (1)，valid 加 1，变为 2。
   • right 指向 'E'：忽略。
   • right 指向 'C'：window['C'] 变为 1。window['C'] (1) == need['C'] (1)，valid 加 1，变为 3。
   • 此时 valid (3) == len(need) (3)，窗口 [A, D, O, B, E, C] 包含了 t 的所有字符。我们记录下这个解：start=0, len_sub=6-0=6。

3. 步骤二：收缩窗口（移动 left）

   • 现在开始移动 left，试图找到更小的窗口。
   • left 指向 'A'：将 'A' 移出窗口，window['A'] 减为 0。此时 window['A'] (0) < need['A'] (1)，字符 'A' 的条件不再满足，valid 减 1，变为 2。
   • 由于 valid (2) < 3，窗口不再满足条件。停止收缩。此时窗口是 [D, O, B, E, C]。

4. 步骤三：继续扩大窗口（移动 right）

   • right 继续右移，经过 'O', 'D', 'E'，都忽略。
   • right 指向 'B'：window['B'] 变为 2。window['B'] (2) 已经大于 need['B'] (1)，所以 valid 不变（'B' 的条件早已满足）。
   • right 指向 'A'：window['A'] 变为 1。window['A'] (1) == need['A'] (1)，valid 加 1，变为 3。
   • 此时 valid 又等于 3，窗口 [D, O, B, E, C, O, D, E, B, A, N, C] 再次满足条件。但当前窗口长度 11-1=10 大于之前记录的 len_sub=6，所以不更新结果。

5. 步骤四：再次收缩窗口（移动 left）

   • 移动 left，移出 'D', 'O', 'B', 'E', 'C', 'O', 'D', 'E'。这些字符要么不在 t 中，要么移出后数量依然大于等于需求（如 'B' 从2变1，依然满足），所以 valid 保持 3。
   • 当 left 移动到 'B' 时，窗口变为 [B, A, N, C]。此时长度 12-8=4 小于之前的 len_sub=6，我们更新结果：start=8, len_sub=4。
   • 继续移动 left，移出 'B'：window['B'] 从1变为0。window['B'] (0) < need['B'] (1)，valid 减 1，变为 2。停止收缩。

6. 步骤五：最后一步

   • right 已到末尾，无法继续扩大。算法结束。

7. 最终结果：

   • 我们记录的最小窗口起始位置是 start=8，长度是 len_sub=4。
   • 所以子串是 s[8:8+4]，即 "BANC"。

第四步：代码实现（Python）

import collections

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 初始化 need 和 window 字典
        need = collections.defaultdict(int)
        window = collections.defaultdict(int)
        
        # 构建 need 字典，记录 t 中每个字符的需求量
        for c in t:
            need[c] += 1
        
        # 初始化双指针和关键变量
        left, right = 0, 0
        valid = 0  # 满足条件的字符种类数
        
        # 记录最小覆盖子串的起始索引和长度
        start = 0
        min_len = float('inf')
        
        # 开始滑动窗口
        while right < len(s):
            # c 是将移入窗口的字符
            c = s[right]
            # 右移窗口
            right += 1
            
            # 进行窗口内数据的一系列更新
            if c in need:
                window[c] += 1
                # 如果某个字符的数量达到了需求，则 valid 加一
                if window[c] == need[c]:
                    valid += 1
            
            # 判断左侧窗口是否要收缩（当窗口已满足条件时）
            while valid == len(need):
                # 在这里更新最小覆盖子串
                if right - left < min_len:
                    start = left
                    min_len = right - left
                
                # d 是将移出窗口的字符
                d = s[left]
                # 左移窗口
                left += 1
                
                # 进行窗口内数据的一系列更新
                if d in need:
                    # 如果移出前刚好满足，移出后就不满足了
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        
        # 返回结果
        return "" if min_len == float('inf') else s[start:start+min_len]

第五步：复杂度分析

• 时间复杂度：O(|s| + |t|)
  • 左右指针 left 和 right 各自遍历字符串 s 一次，每个字符最多被进入和离开窗口各一次，所以是 O(|s|)。
  • 初始化 need 字典需要遍历 t，是 O(|t|)。
• 空间复杂度：O(|t|)
  • 主要是 need 和 window 字典的空间，最坏情况下 t 中每个字符都不同，所以是 O(|t|)。

总结

LeetCode 76 「最小覆盖子串」 的精髓在于：

1. 滑动窗口框架：使用 left 和 right 指针遍历所有可能的子串。
2. 哈希表记录需求：用 need 和 window 字典来精确跟踪字符数量。
3. valid 计数器：这是判断窗口是否满足条件的关键技巧，它避免了每次都比较整个字典，将判断操作优化到 O(1)。

掌握这个模板，你就能解决一大类子串搜索/匹配问题。希望这个循序渐进的讲解能让你彻底理解这道题！