76. 最小覆盖子串

Difficulty
Hard
Tags
滑动窗口
双指针
URL
https://leetcode-cn.com/problems/minimum-window-substring/
Star
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
  • 1 <= s.length, t.length <= 105
  • s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

滑动窗口

思路
不同于之前题目的是，本题每个窗口中存放的不再是完整的从left到right的全部字符串了，只存放了需要用的的，即t中出现的字符串。此外为了方便统计window的字符是否满足t中对应字符出现的次数，另外建立了一个字典need.
按照滑动窗口的策略，一直向右扩张，每次来一个字符，先判断一下是否应该放到window中，然后判断该字符是否满足要求，如果满足那就valid+=1，然后再判断是否需要收缩窗口。
题解
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = collections.defaultdict(int)
        window = collections.defaultdict(int)

        for c in t:
            need[c] += 1

        left, right = 0, 0
        valid = 0
        start, length = 0, float('inf')

        while right < len(s):
            cur = s[right]
            right += 1
            if cur in need:
                window[cur] += 1
                if window[cur] == need[cur]:
                    valid += 1
            print(left, right)
            while valid == len(need):
                if length > right - left:
                    length = right - left
                    start = left
                dele = s[left]
                left += 1
                if dele in need:
                    if window[dele] == need[dele]:
                        valid -= 1
                    window[dele] -= 1

        return s[start:start+length] if length!=float('inf') else ""