76. 最小覆盖子串 (Hard)

专题归类： 02-双指针与滑动窗口 · 01-哈希表 LeetCode 链接： https://leetcode.cn/problems/minimum-window-substring/

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

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

注意：

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

示例：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：涵盖 "A"、"B"、"C" 的最小子串是 "BANC"

补充说明：

s 和 t 的长度范围：1 <= s.length, t.length <= 10^5
s 和 t 由英文字母组成（大小写敏感）

题目详细分析

数据范围含义：

s 最大 10^5，t 最大 10^5。暴力法——枚举所有子串 O(n^2 × m) 完全不可行。
需要 O(n) 或 O(n log n) 的解法。
字符集大小写敏感，意味着 ‘A’ 和 ‘a’ 是不同的字符。总共有 26×2 = 52 个可能的字符（仅限字母），但为了通用性，用哈希表而非固定数组更稳妥。

核心要求：

涵盖（cover）意味着子串中每个字符的数量 ≥ t 中的数量。不是等号，是 ≥。子串可以多出 t 中不存在的字符，也可以多出 t 中已有但超量的字符。
最小意味着子串长度最短。
子串必须是连续的（substring，不是 subsequence）。

边界条件：

如果 len(t) > len(s)，直接返回 ""（不可能有解）。
如果 t 是 s 的子串（如 s = “ABC”, t = “ABC”），返回 t 本身。
t 可能包含重复字符（如 t = “AABC”），需要准确统计每个字符的需求量。
s 中可能有 t 中不存在的字符，它们不影响”覆盖”条件，但会影响窗口大小。

隐藏条件：

本题是滑动窗口中最复杂的一类——“不定长 + 多条件满足”。
关键在于用一个 valid 变量来追踪”有多少种字符已经满足了需求”，而不是检查每个字符的计数。
窗口的扩大和缩小完全由”是否已覆盖”这个条件驱动。
唯一解意味着找到后可以直接返回（但通常还是遍历完整个 s，因为需要保证最小）。

小白版直白理解

想象你在超市买东西，你有一张购物清单（t），上面写着要买的东西和数量（比如 A 两个、B 一个、C 三个）。超市的货架是一条长带子（s），上面摆满了各种商品，你有能力从中间连续取一段商品。

你要找最短的一段连续货架，这段货架上的商品能满足你的购物清单（每种商品的数量至少等于清单上的数量）。

笨办法： 从货架的每个位置开始，往右看，检查是否能满足清单，直到找到最短的。每个位置都要看一长段，非常慢。

聪明办法（滑动窗口）： 你用一个移动的”购物车”（窗口）在货架上从左往右推：

先往购物车里不断放东西（右指针右移），直到车里有了清单上需要的所有东西（覆盖了）。
然后从左边往外扔东西（左指针右移），看能不能扔一些出去但仍然满足清单。每次扔之前，看看当前购物车的大小是不是更小了，记录下来。
如果扔掉一个必需品导致不满足了，就回到第 1 步，继续往右放东西。
最终你就会找到最短的那段。

解题思路

思路一：滑动窗口 + 哈希表 + valid 变量（推荐，标准模板）

核心想法： 本题是滑动窗口的集大成者，需要处理”不定长”、“多条件计数”、“最优解搜索”三个难点。

关键数据结构：

need：字典，记录 t 中每个字符的需求数量。
window：字典，记录窗口内每个字符的出现数量。
valid：整数，记录”已满足需求的字符种类数”。当 valid == len(need) 时，说明窗口已覆盖 t。

三问法分析：

什么时候扩大窗口？ 还没覆盖 → 右移 right，扩大窗口。
什么时候缩小窗口？ 已经覆盖了 → 左移 left，找更小的窗口。
什么时候更新答案？ 缩小窗口时（因为缩小意味着找到了更小的覆盖子串）。

from collections import defaultdict
 
def minWindow(s, t):
    """
    滑动窗口 + 哈希表 + valid 变量
    
    步骤：
    1. 统计 t 中每个字符的需求量
    2. 右指针扩展窗口直到覆盖所有字符
    3. 左指针收缩窗口寻找最小覆盖子串
    4. 记录每次收缩前的最优解
    
    valid: 记录已满足需求数量的字符种类数
    当 valid == len(need) 时，窗口已覆盖 t
    """
    need = defaultdict(int)
    for ch in t:
        need[ch] += 1
    
    window = defaultdict(int)
    valid = 0          # 已满足的字符种类数
    left = 0
    
    # 记录最小覆盖子串的起始位置和长度
    start = 0
    length = float('inf')
    
    for right, ch in enumerate(s):
        # ========== 扩大窗口 ==========
        if ch in need:
            window[ch] += 1
            if window[ch] == need[ch]:
                # 该字符的数量已经满足了需求
                valid += 1
        
        # ========== 缩小窗口 ==========
        while valid == len(need):
            # 更新最优解（缩小前，当前窗口是候选）
            if right - left + 1 < length:
                start = left
                length = right - left + 1
            
            # 左指针右移，缩小窗口
            d = s[left]
            left += 1
            
            if d in need:
                if window[d] == need[d]:
                    # 移除了一个必需的字符，valid 减少
                    valid -= 1
                window[d] -= 1
    
    return s[start:start + length] if length != float('inf') else ""

思路二：滑动窗口 + 单个计数器（简单版）

对于只包含字母的字符串，可以用数组替代哈希表，但思路完全一致。

def minWindow_array(s, t):
    """
    数组版滑动窗口（仅限字母）
    用固定 128 长度的数组代替哈希表（覆盖 ASCII）
    """
    if len(t) > len(s):
        return ""
    
    need = [0] * 128
    for ch in t:
        need[ord(ch)] += 1
    
    window = [0] * 128
    need_kinds = sum(1 for x in need if x > 0)
    valid = 0
    left = 0
    start, length = 0, float('inf')
    
    for right, ch in enumerate(s):
        idx = ord(ch)
        if need[idx] > 0:
            window[idx] += 1
            if window[idx] == need[idx]:
                valid += 1
        
        while valid == need_kinds:
            if right - left + 1 < length:
                start = left
                length = right - left + 1
            
            left_idx = ord(s[left])
            if need[left_idx] > 0:
                if window[left_idx] == need[left_idx]:
                    valid -= 1
                window[left_idx] -= 1
            left += 1
    
    return s[start:start+length] if length != float('inf') else ""

易错点

valid 变量的含义： valid 表示的是”已满足需求的字符种类数”，不是”窗口中字符总数”，也不是”已满足的字符个数”。当 window[ch] == need[ch] 时 valid 才加一，当 window[ch] < need[ch] 时才减一。
valid 加减的对称性： 扩大窗口时，window[ch] 从 need[ch] - 1 变为 need[ch] 时 valid += 1。缩小窗口时，window[ch] 从 need[ch] 变为 need[ch] - 1 时 valid -= 1。这两个操作必须对称。
更新答案的位置： 答案在缩小窗口前更新，因为此时窗口刚好覆盖 t 且可能最小。不要在缩小后更新（那时候已经不覆盖了）。
字符不在 t 中： 不需要加入 window 字典（因为它不影响 valid），但加入也可以（反正不会达到 need），不影响结果但浪费空间。
检查是否找到结果： 注意 length 的初始值应该是 float('inf')（或 len(s) + 1），返回时检查 length 是否被更新过。不能用 0 或 len(s) 作为未找到的标志（因为可能真的有一个长度为 0 或 len(s) 的子串）。
t 中可能有重复字符： need 字典记录的是每个字符的需求数量，不是种类数。valid 的最大值是 len(need)（不同种类数），不是 len(t)。

框架提炼

复杂滑动窗口终极模板：

这是最完整的滑动窗口模板，适用于”找满足条件的最短/最长子串”类问题。

from collections import defaultdict
 
def sliding_window_complex(s, target):
    """
    复杂滑动窗口终极模板
    """
    # ===== 1. 初始化 =====
    need = defaultdict(int)      # 目标需求
    for ch in target:
        need[ch] += 1
    
    window = defaultdict(int)    # 窗口计数
    valid = 0                    # 已满足的「条件」数量
    left = 0
    
    # 结果记录
    result_start = 0
    result_length = float('inf')  # 找最短用 inf，找最长用 0
    
    # ===== 2. 滑动窗口 =====
    for right, val in enumerate(s):
        # ----- 2a. 扩大窗口 -----
        if val in need:
            window[val] += 1
            if window[val] == need[val]:
                valid += 1  # 该条件已满足
        
        # ----- 2b. 缩小窗口 -----
        while valid == len(need):  # 所有条件都满足时缩小
            # 更新最优解（找最短：缩小前更新；找最长：扩大后更新）
            if right - left + 1 < result_length:
                result_start = left
                result_length = right - left + 1
            
            # 缩小窗口
            d = s[left]
            left += 1
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1
    
    # ===== 3. 返回结果 =====
    return s[result_start:result_start + result_length] \
        if result_length != float('inf') else ""

模板变体的关键参数：

参数	找最小（本题）	找最大（如第 3 题）
result_length 初值	`float('inf')`	`0`
何时更新答案	缩小窗口前（此时满足条件且最小）	扩大窗口后（此时满足条件且最大）
收缩条件	`valid == len(need)`	`valid < len(need)`（不满足时收缩）

关联题目

3-无重复字符的最长子串 — 同属不定长滑动窗口，但 3 号题约束是”无重复”（收缩条件是有重复），本题约束是”全覆盖”（收缩条件是已覆盖）。两者构成了滑动窗口”求最长/求最短”的经典对比
438-找到字符串中所有字母异位词 — 同样是字符计数 + 窗口比较，但 438 是定长窗口（窗口大小固定为 len(p)），本题是不定长窗口。感受二者的区别有助于深入理解滑动窗口
567-字符串的排列 — 本题的简化版，判断 s2 中是否包含 s1 的排列。排列本质上就是定长覆盖子串（长度必须等于 s1），比本题简单

description	给你一个字符串 s 和一个字符串 t。
tags	02-双指针与滑动窗口, 01-哈希表

力扣百题通

浏览内容

76. 最小覆盖子串 (Hard)

76. 最小覆盖子串 (Hard)

题目描述

题目详细分析

小白版直白理解

解题思路

思路一：滑动窗口 + 哈希表 + valid 变量（推荐，标准模板）

思路二：滑动窗口 + 单个计数器（简单版）

易错点

框架提炼

关联题目

关系图谱

目录

反向链接