76. 最小覆盖子串

题目

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

测试用例保证答案唯一。

示例 1：

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

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

m == s.length
n == t.length
1 <= m, n <= 10⁵
s 和 t 由英文字母组成

题解

这是一个经典的 滑动窗口 (Sliding Window) 问题

我们需要维护一个动态的窗口 [left, right]：

右移扩大：不断移动 right 指针，将字符加入窗口，直到窗口包含了 t 中所有的字符。
左移收缩：一旦窗口满足条件，尝试移动 left 指针缩小窗口，剔除左边多余的字符，直到窗口不再满足条件为止。
更新结果：在每次窗口满足条件且尝试收缩的过程中，记录最小的窗口长度。

关键点：如何判断窗口是否“满足条件”？

使用 哈希表 (Hash Map) 或数组（因为字符通常是 ASCII）。

required：记录还需要匹配的字符总数。

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""

    # 初始化哈希表
    hash_map = {}
    for char in t:
        hash_map[char] = hash_map.get(char, 0) + 1
    
    n = len(s)
    left = 0
    right = 0
    required = len(t)
    
    # 优化点：只记录长度和起始索引，不存字符串
    min_len = float('inf')
    start_index = 0
    
    while right < n:
        # 进窗口
        if s[right] in hash_map:
            if hash_map[s[right]] > 0:
                required -= 1
            hash_map[s[right]] -= 1
        
        # 满足条件，尝试收缩
        while required == 0:
            # 优化点：更新最小长度和起始位置
            current_len = right - left + 1
            if current_len < min_len:
                min_len = current_len
                start_index = left
            
            # 出窗口
            if s[left] in hash_map:
                hash_map[s[left]] += 1
                # 只有当原本需要的字符数量变回 >0 时，required 才 +1
                if hash_map[s[left]] > 0:
                    required += 1
            left += 1
        
        right += 1
    
    # 最后切片一次
    return "" if min_len == float('inf') else s[start_index : start_index + min_len]

#

!

76. 最小覆盖子串

题目

题解