哈希算法题目：最小覆盖子串（滑动窗口 + 哈希表）

题目描述
给定一个字符串 s 和一个字符串 t，请你找出 s 中包含 t 的所有字符的最小子串。如果 s 中不存在这样的子串，则返回空字符串 ""。

示例 1
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：s 中包含 'A'、'B'、'C' 的最短子串是 "BANC"。

示例 2
输入：s = "a", t = "a"
输出："a"

示例 3
输入：s = "a", t = "aa"
输出：""
解释：t 中有两个 'a'，但 s 中只有一个 'a'，所以不存在符合条件的子串。

注意

• 如果存在多个长度相同的最小子串，返回任意一个即可。
• 你需要同时考虑字符的出现次数，而不仅仅是字符的存在。
• 你可以假设字符串 s 和 t 只包含英文字母，且 s 的长度 ≥ t 的长度。

解题过程

步骤 1：问题理解
目标是在字符串 s 中找到一个最短的连续子串，使得这个子串至少包含 t 中的所有字符，且每个字符的数量不少于 t 中该字符的数量。
例如，t = "AABC" 意味着子串必须至少包含 2 个 'A'、1 个 'B' 和 1 个 'C'。

关键点

• 必须考虑字符的频数，而不仅仅是存在。
• 子串是连续的，所以可以用滑动窗口思想。
• 用哈希表来记录 t 中每个字符需要的数量，以及当前窗口中每个字符的实际数量。

步骤 2：算法思路

1. 用两个哈希表（字典）：
   • need：记录 t 中每个字符需要的数量。
   • window：记录当前窗口中每个字符的数量。
2. 使用双指针 left 和 right 表示滑动窗口的左右边界，初始都从 0 开始。
3. 移动右指针 right 扩大窗口，直到窗口中的字符满足 t 的所有字符需求。
4. 一旦满足条件，尝试移动左指针 left 缩小窗口，以寻找更小的满足条件的子串，同时更新最小子串的起始位置和长度。
5. 当窗口不再满足条件时，继续移动右指针，重复上述过程，直到 right 到达 s 的末尾。

如何判断窗口满足条件？
我们可以引入一个变量 valid，表示当前窗口中已经满足数量要求的字符种类数。例如，t 中有 3 种字符，当窗口中这 3 种字符的数量都 ≥ t 中对应字符的数量时，valid 才会等于 3，表示窗口满足条件。

步骤 3：详细步骤

初始化

from collections import defaultdict

need = defaultdict(int)  # t 中各字符需要的数量
window = defaultdict(int)  # 当前窗口中各字符的数量
for ch in t:
    need[ch] += 1
need_cnt = len(need)  # t 中不同字符的种类数
valid = 0  # 窗口中满足数量要求的字符种类数
left = 0
min_len = float('inf')
start = 0

滑动窗口过程

1. 右指针 right 从 0 遍历到 len(s)-1：

   • 将 s[right] 加入窗口：

     ch = s[right]
     if ch in need:  # 只关心 t 中出现的字符
         window[ch] += 1
         if window[ch] == need[ch]:
             valid += 1
     

   • 当 valid == need_cnt 时，表示窗口已满足 t 的所有字符需求，此时尝试收缩左指针：

     while valid == need_cnt:
         # 更新最小子串
         if right - left + 1 < min_len:
             min_len = right - left + 1
             start = left
         # 移出左指针字符
         ch_out = s[left]
         if ch_out in need:
             if window[ch_out] == need[ch_out]:
                 valid -= 1
             window[ch_out] -= 1
         left += 1
     

2. 循环结束后，如果 min_len 仍是无穷大，则返回空字符串，否则返回 s[start:start+min_len]。

步骤 4：示例推演
以 s = "ADOBECODEBANC", t = "ABC" 为例：

• need = {'A':1, 'B':1, 'C':1}, need_cnt=3
• right 移动到 5 ("ADOBEC") 时，窗口包含 A、B、C 各一个，valid=3，满足条件，记录长度 6。
• 收缩 left 到 1 ("DOBEC")，此时 A 移出，valid=2，不再满足。
• 继续移动 right 直到 10 ("ADOBECODEBAN")，仍缺 C。
• 最后 right=12 ("ADOBECODEBANC") 时，窗口重新满足，收缩 left 找到 "BANC" (长度 4)，为最终结果。

步骤 5：复杂度分析

• 时间复杂度：O(|s| + |t|)，因为左右指针各遍历一次 s。
• 空间复杂度：O(|t|)，主要是两个哈希表存储 t 的字符频数。

步骤 6：代码实现

from collections import defaultdict

def minWindow(s: str, t: str) -> str:
    need = defaultdict(int)
    window = defaultdict(int)
    for ch in t:
        need[ch] += 1
    need_cnt = len(need)
    
    left = 0
    valid = 0
    min_len = float('inf')
    start = 0
    
    for right, ch in enumerate(s):
        if ch in need:
            window[ch] += 1
            if window[ch] == need[ch]:
                valid += 1
        
        while valid == need_cnt:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                start = left
            ch_out = s[left]
            if ch_out in need:
                if window[ch_out] == need[ch_out]:
                    valid -= 1
                window[ch_out] -= 1
            left += 1
    
    return "" if min_len == float('inf') else s[start:start+min_len]