76. 最小覆盖子串

题目链接：76. 最小覆盖子串

题目描述

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

注意：

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

核心思考：滑动窗口寻找最小覆盖

这道题是经典的滑动窗口 (Sliding Window) 应用题。

关联题目： 本题的解法框架与 209. 长度最小的子数组 非常相似。两者同根同源，都使用了滑动窗口这种双指针技巧：右指针不断向右移动来扩大窗口以积累状态满足条件，一旦满足条件，左指针就开始向右移动来缩小窗口，以此来寻找“最小”的区间范围。

具体到本题，我们需要寻找涵盖 t 的最小子串。我们的核心逻辑如下：

1. 右指针 (right) 不断向右枚举子串的右端点。如果当前新加入窗口的字符在 t 中有出现，我们就将其统计进入窗口状态（c_s）。
2. 左指针 (left) 则在窗口涵盖了 t 时进行收缩。当当前窗口内的字符集及其数量完全覆盖了 t 的需求（即 c_s >= c_t），说明找到了一个有效解。此时我们更新最短子串的左右端点，然后开始向右移动左指针（并顺便移除左指针所指向的字符），把窗口缩小，寻找是否还有更短的有效解。

细节

Python 提供的 Counter 模块具有一个非常强大的重载特性：对于两个计数器对象，c_s >= c_t 可以直接用来判断字典 c_s 中包含的字符种类和数量是否完全覆盖了 c_t。这极大地简化了代码逻辑。

解题思路 (Python)

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 我们枚举 s 子串的右端点 right（子串最后一个字母的下标），如果子串涵盖 t，就不断移动左端点 left 直到不涵盖为止。在移动过程中更新最短子串的左右端点。
        c_s = Counter() # 初始化为空
        c_t = Counter(t)
        left = 0
        ans_left = -1
        ans_right = len(s)

        for right, x in enumerate(s):
            c_s[x] += 1
            while c_s >= c_t:
                if right - left < ans_right - ans_left:
                    ans_left,ans_right = left,right
                c_s[s[left]] -= 1
                left += 1
        if ans_left < 0:
            return ""
        else:
            return s[ans_left:ans_right+1]

复杂度分析

• 时间复杂度：$O(|s| \cdot |\Sigma| + |t|)$，其中 $|s|$ 和 $|t|$ 分别为字符串 s 和 t 的长度，$|\Sigma|$ 代表字符集的大小。对于字符串 s 的每个字符，我们在外层循环中执行进窗口，在内存 while 循环中最多执行出窗口。但注意到我们直接利用了 c_s >= c_t 的比较，该比较会遍历两个哈希表判定状态，在最坏情况下需要消耗 $O(|\Sigma|)$ 的时间。
• 空间复杂度：$O(|\Sigma|)$。我们利用了哈希表来记录字符频数，其空间占用取决于字符集的大小。对于英文字母字符集，空间可以视为一个小常数。