[76][困难][滑动窗口] 最小覆盖子串

题目描述

76. 最小覆盖子串

给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

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

提示：

• 如果 S 中不存这样的子串，则返回空字符串 ""。

• 如果 S 中存在这样的子串，我们保证它是唯一的答案。

解题思路

滑动窗口的思路. 定义两个指针, 右指针扩展, 左指针收缩. 在任意时刻, 只移动一个指针. 使用哈希表记录窗口中T的每个字符出现的次数, 之所以记录次数, 是因为T中可能有重复的字母.

首先扩展右指针, 直到窗口中包含了所有T中的所有字符. 然后收缩左指针, 直到抛弃了某个字符后, 窗口不能再覆盖T中的所有字符.

上面是一个大循环的步骤, 重复这些步骤, 直到右指针越界.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n = len(s)

        t_map = Counter(t)
        t_set = set(t_map.keys())
        t_count = sum(t_map.values())

        c_map, c_count = dict(), 0
        max_len, res = float('inf'), ''
        left = right = 0
        while right < n:
            c = s[right]
            right += 1

            if c in t_set:
                last_count = c_map.get(c, 0)
                if last_count < t_map[c]:
                    c_count += 1
                c_map[c] = c_map.get(c, 0) + 1
                if c_count == t_count:
                    if right - left < max_len:
                        max_len = right - left
                        res = s[left: right]

            while c_count == t_count:
                if right - left < max_len:
                    max_len = right - left
                    res = s[left: right]

                c = s[left]
                left += 1

                if c in t_set:
                    last_count = c_map.get(c, 0)
                    if last_count <= t_map[c]:
                        c_count -= 1
                    c_map[c] = c_map[c] - 1
                    if c_count < t_count:
                        break
        return res