力扣热门100题之最小覆盖子串【困难】【滑动窗口】

**力扣热门100题之最小覆盖子串**

**难度:** 困难**类型:** 滑动窗口**描述:**

给定两个字符串 `s` 和 `t`,返回 `s` 中的最小覆盖子串 `t`。如果 `t` 无法在 `s` 中找到，则返回一个空字符串。

**示例1:**

输入:`s = "ADOBECODEBANC"、`t = "ABC"`
输出:`"ABC"`

**示例2:**

输入:`s = "a"、`t = "aa"`
输出:`""`

**思路:**

本题使用滑动窗口法求解。首先，我们需要定义一个哈希表 `need` 来存储字符串 `t` 中每个字符的出现次数。然后，我们遍历字符串 `s`,并在每次移动窗口时更新 `window` 哈希表和覆盖子串长度。

**代码:**

from collections import defaultdictclass Solution:
 def minWindow(self, s: str, t: str) -> str:
 if not s or not t:
 return ""

 need = defaultdict(int)
 for char in t:
 need[char] +=1 left =0 right =0 count = len(t)
 min_len = float('inf')
 min_str = ""

 while right < len(s):
 if s[right] in need:
 need[s[right]] -=1 if need[s[right]] >=0:
 count -=1 while count ==0:
 if right - left +1 < min_len:
 min_len = right - left +1 min_str = s[left:right+1]

 if s[left] in need:
 need[s[left]] +=1 if need[s[left]] >0:
 count +=1 left +=1 right +=1 return min_str