1 題目

給你一個字符串 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 的子串中，
因此沒有符合條件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s 和 t 由英文字母組成

2 解答

滑動窗口做法

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        count_s = Counter()
        count_t = Counter(t)
        left = 0
        ansleft = -1
        ansright = len(s)

        for right , val in enumerate(s):
            count_s[val] += 1
            while count_s >= count_t: #涵蓋
                if right - left < ansright - ansleft:
                    ansleft ,  ansright = left , right
                count_s[s[left]] -= 1
                left += 1
        return "" if ansleft <0 else s[ansleft : ansright+1]