最小覆盖子串 -

题目

最小覆盖子串

信息

类型：问答
难度：⭐⭐

考点

滑动窗口,哈希表,双指针

快速回答

给定字符串 S 和模式串 T，在 S 中找出包含 T 所有字符的最短连续子串。

解决步骤：

使用哈希表 need 统计 T 中字符出现频率
初始化双指针 left = right = 0 和窗口哈希表 window
移动右指针扩大窗口，当窗口包含 T 所有字符时：
- 更新最小子串位置和长度
- 移动左指针缩小窗口直到不满足条件
返回最小覆盖子串

时间复杂度： O(|S| + |T|)

解析

问题描述

给定字符串 S 和模式串 T，在 S 中找出包含 T 所有字符（包括重复字符）的最短连续子串。如果不存在则返回空字符串。

示例：
输入：S = "ADOBECODEBANC", T = "ABC"
输出："BANC"

算法原理

使用滑动窗口配合双指针和哈希表：

哈希表统计：用 need 哈希表记录 T 中每个字符的出现次数
双指针维护窗口：
- left 和 right 指针表示当前窗口 [left, right)
- valid 计数器记录窗口中满足 need 条件的字符数量
窗口扩展与收缩：
- 移动 right 扩大窗口，更新窗口哈希表 window
- 当 valid == need.size() 时：
  - 记录当前最小子串
  - 移动 left 缩小窗口直到条件不满足

代码实现（Python）

from collections import defaultdict

def minWindow(s: str, t: str) -> str:
    need = defaultdict(int)
    for c in t:
        need[c] += 1

    window = defaultdict(int)
    left, right = 0, 0
    valid = 0  # 满足条件的字符数
    start, min_len = 0, float('inf')  # 结果记录

    while right < len(s):
        # 扩大右边界
        c = s[right]
        right += 1
        if c in need:
            window[c] += 1
            if window[c] == need[c]:
                valid += 1

        # 满足条件时收缩左边界
        while valid == len(need):
            # 更新最小覆盖子串
            if right - left < min_len:
                start = left
                min_len = right - left

            # 缩小窗口
            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]

最佳实践

哈希表优化：使用 defaultdict 避免键不存在判断
valid 计数器：避免每次遍历 need 检查条件，提升效率
边界处理：当窗口移动时注意字典键的存在性检查

常见错误

遗漏重复字符：未正确处理 T 中重复字符（如 T="AAB"）
无效移动：在 valid 不足时收缩窗口导致漏解
指针更新顺序错误：先更新指针还是先更新哈希表？
未初始化边界值：min_len 未设初始极大值导致结果错误

扩展知识

变体问题：
- 最长无重复子串（LeetCode 3）
- 字符串排列（LeetCode 567）
- 找到所有字母异位词（LeetCode 438）
优化方向：当字符串包含大量非目标字符时，可先过滤无关字符
复杂度证明：虽然含嵌套循环，但每个字符最多被访问两次（O(n)）