# 最小覆盖子串

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E5%9B%B0%E9%9A%BE\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#困难) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#滑动窗口)

**问题简述**

```
给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。
```

> [最小覆盖子串\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac)

**思路：滑动窗口**

* 应用模板比较复杂的一题；

<details>

<summary><strong>滑动窗口模板</strong></summary>

```python
l = r = 0  # 初始化 [l, r] 闭区间
while r < N:
    # 更新窗口
    while check():  # 满足要求进入循环，不满足退出
        # 更新答案
        l += 1  # 移动左边界
    r += 1  # 移动右边界
```

</details>

<details>

<summary><strong>Python</strong></summary>

```python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        
        from collections import Counter, defaultdict
        
        l, r = 0, 0
        N = len(S)
        ret = S  # 初始化为最大的可能，但是注意，可能有无结果的情况，所以还需要一个变量记录答案是否存在
        flag = -1  # 记录是否出现过匹配串，避免无答案的情况
        need = Counter(T)
        used = defaultdict(int)
        
        def check():  # 检验是否满足情况
            for k, v in need.items():
                if k not in used or used[k] < need[k]:
                    return False
            return True
        
        while r < N:
            used[S[r]] += 1
            while check():
                flag = 1
                if r - l < len(ret):
                    ret = S[l: r + 1]
                used[S[l]] -= 1
                l += 1
            r += 1
        
        return ret if flag != -1 else ''
```

</details>