最小覆盖子串

标签: 哈希表 字符串 滑动窗口

难度: Hard

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

注意：

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

示例 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 <= 105
  • s 和 t 由英文字母组成
进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

Submission

运行时间: 188 ms

内存: 15.3 MB

from collections import defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = defaultdict(int)
        for char in t:
            need[char] += 1
        
        window = defaultdict(int)
        left = right = 0
        valid = 0
        start = 0
        length = 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
            
            print(left, right, valid)

            while valid == len(need):
                if right - left < length:
                    length = right - left
                    start = left
                
                d = s[left]
                left += 1
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        return '' if length == float('inf') else s[start:start+length]

Explain

题解采用了滑动窗口的策略来寻找包含字符串t所有字符的最小子串。首先，使用字典need记录字符串t中各字符的数量。另外使用窗口字典window记录当前窗口中各字符的数量。通过移动右指针right扩展窗口，当窗口中包含t的所有字符后（即窗口中的字符数量满足t的需求），尝试通过移动左指针left缩小窗口，同时更新记录最小窗口的start和length变量。窗口有效时进行缩小操作，不再有效时继续扩展右指针。最后，根据记录的start和length输出最小覆盖子串。

时间复杂度: O(m + n)

空间复杂度: O(1)

from collections import defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 字典记录t中每个字符需要的数量
        need = defaultdict(int)
        for char in t:
            need[char] += 1
        
        # 当前窗口中各字符的数量
        window = defaultdict(int)
        # 左右指针及窗口内满足条件的字符类型数
        left = right = valid = 0
        # 记录最小子串的起始位置和长度
        start = 0
        length = 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 < length:
                    length = right - left
                    start = left
                
                # 缩小左边界
                d = s[left]
                left += 1
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        # 如果未找到合适的子串，返回空字符串
        return '' if length == float('inf') else s[start:start+length]

Explore

在滑动窗口算法中，通过使用两个字典`need`和`window`来分别记录字符串t中每个字符需要的数量和当前窗口中各字符的实际数量。同时，使用一个计数器`valid`来记录当前窗口中满足t中字符需求的字符类型数。每当一个字符在窗口中的数量达到其在t中的需求时，`valid`计数器加1。当`valid`的值等于`need`字典中键的数量（即t中不同字符的数量）时，说明窗口已经包含了t的所有字符。

当窗口首次包含了t的所有字符后，此时的窗口是一个可能的解，但可能不是最小解。接下来尝试通过移动左指针`left`来缩小窗口的大小。这是为了探索是否存在更小的窗口同样包含t的所有字符。每次移动左指针时，都会检查缩小后的窗口是否仍满足条件，这通过减少左指针字符的数量并更新`valid`值来实现。只有当窗口仍然有效时（即包含t的所有字符），我们才更新记录最小子串的起始位置和长度。这种策略通过不断尝试减小窗口的长度，直到不再满足条件，从而确保找到的子串是最小的。

在移动左指针`left`减小窗口大小时，会减少离开窗口字符的数量。对于每一个离开窗口的字符`d`，窗口字典`window`中该字符的数量减1。如果减少后的数量小于在`need`字典中记录的需求数量，并且该字符是t中的字符，则`valid`计数器减1。这意味着窗口不再满足包含t的所有字符的条件。这种处理方式确保了每次缩小窗口时，我们都会准确地评估窗口的有效性（是否包含t的所有字符）。

如果字符串s中包含t中未出现的字符，这些字符在`need`字典中的计数为0，因此在维护`window`字典时，这些字符虽然会被记录其数量，但不会影响`valid`计数器的值。窗口的扩展和缩小仅考虑那些在`need`字典中存在的字符。这意味着，虽然这些未出现在t中的字符会被计入窗口，但它们不影响窗口是否满足覆盖子串的条件。这样的处理简化了算法的逻辑，使其专注于t中的字符。