最小覆盖子串

难度: Hard

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC" 
解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3：

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

提示：

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

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

注意：本题与主站 76 题相似（本题答案不唯一）：https://leetcode-cn.com/problems/minimum-window-substring/

Submission

运行时间: 56 ms

内存: 16.3 MB

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ###滑动窗口+双指针+计数
        dic=collections.defaultdict(int)
        for tt in t:
            dic[tt]+=1
        cnt=len(t)
        res=(0,len(s))
        i,j=0,0
        while j<len(s):
            if dic[s[j]]>0:
                cnt-=1
            dic[s[j]]-=1
            if cnt==0:
                while dic[s[i]]<0:
                    dic[s[i]]+=1
                    i+=1
                if j-i<res[1]-res[0]:res=(i,j)
                dic[s[i]]+=1
                i+=1
                cnt+=1
            j+=1
        return s[res[0]:res[1]+1] if res[1]!=len(s) else ''

Explain

这道题使用了滑动窗口和双指针的方法。首先，使用一个字典记录字符串t中每个字符的数量。然后，使用两个指针i和j来表示当前的滑动窗口，初始时都指向s的开头。随着j的向右移动，如果当前字符在t中，就减少字典中对应字符的数量，并且减少计数器cnt的值。当cnt变为0时，说明当前窗口已经包含了t中的所有字符。接着，尝试移动左指针i，直到窗口不再包含t中的所有字符。在这个过程中，记录最小的窗口大小，并更新结果。最后，返回最小覆盖子串。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 滑动窗口+双指针+计数
        dic = collections.defaultdict(int)
        for tt in t:
            dic[tt] += 1
        cnt = len(t)
        res = (0, len(s))
        i, j = 0, 0
        while j < len(s):
            if dic[s[j]] > 0:
                cnt -= 1
            dic[s[j]] -= 1
            if cnt == 0:
                while dic[s[i]] < 0:
                    dic[s[i]] += 1
                    i += 1
                if j - i < res[1] - res[0]:
                    res = (i, j)
                dic[s[i]] += 1
                i += 1
                cnt += 1
            j += 1
        return s[res[0]:res[1] + 1] if res[1] != len(s) else ''

Explore

在字典中记录字符串t中每个字符的数量主要是为了快速判断滑动窗口内的子串是否包含t中的所有字符及其数量。这种方法使得每次移动窗口时，可以直接通过字典查看和更新字符的计数，而不需要每次都重新计算窗口中的字符是否满足条件。与直接遍历s中的字符相比，这种方法大大减少了重复计算，提高了算法的效率。

这里的cnt是一个计数器，初始化为字符串t的长度，即t中字符的总数。每当滑动窗口包括一个t中的字符时，如果这个字符是t中需要的（即在字典中的计数大于0），则cnt减一。当cnt减到0时，意味着窗口已包含t的所有字符且每个字符的数量至少与t中的相等。因此，cnt为0是判断窗口已包含t中所有字符的有效方式。

在移动左指针i以缩小窗口时，需要逐个将i指向的字符从窗口中排除，即将字典中对应字符的计数增加。每次字典中某个字符的计数从负数变为非负数时，如果这个字符是t中的字符，那么这意味着窗口不再包含t中足够的该字符，此时需要停止缩小窗口并移动右指针j继续寻找合适的窗口。这样可以确保窗口在尽可能小的前提下仍然满足包含t的所有字符。