力扣题库第12题：最小覆盖子串

给你一个字符串 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。

答案：

from collections import defaultdict


def minWindow(s: str, t: str) -> str:
    # 记录 t 中每个字符的出现次数
    target_dict = defaultdict(int)
    for char in t:
        target_dict[char] += 1

        # 记录窗口内字符的出现次数
    window_dict = defaultdict(int)

    # 初始化两个指针和最小子串的起始位置和长度
    left, right = 0, 0
    start, min_len = 0, float('inf')

    # 初始化匹配字符的个数
    match = 0

    # 遍历字符串 s
    while right < len(s):
        # 将右指针指向的字符加入窗口
        char = s[right]
        window_dict[char] += 1

        # 如果窗口内该字符的个数等于 t 中该字符的个数，则匹配字符的个数加 1
        if char in target_dict and window_dict[char] == target_dict[char]:
            match += 1

            # 尝试移动左指针，缩小窗口
        while match == len(target_dict):
            # 更新最小子串的起始位置和长度
            if right - left + 1 < min_len:
                start = left
                min_len = right - left + 1

                # 将左指针指向的字符移出窗口
            char = s[left]
            window_dict[char] -= 1

            # 如果窗口内该字符的个数小于 t 中该字符的个数，则匹配字符的个数减 1
            if char in target_dict and window_dict[char] < target_dict[char]:
                match -= 1

                # 移动左指针
            left += 1

            # 移动右指针
        right += 1

        # 如果找到了满足条件的最小子串，则返回它；否则返回空字符串
    return s[start:start + min_len] if min_len != float('inf') else ""
s = "ADOBECODEBANC"
t = "ABC"
print(minWindow(s,t ))