76. Minimum Window Substring

Last updated on Jan 29, 2023

滑動窗口的經典題目，題目要求要找到最短的子字串，裡面包含了 t 字串有的字元。

我們需要想的是窗口增大的時候，需要更新哪些資訊？

我們需要看看該字元有沒有出現在目標裡面，如果有的話，增加計數
如果我們已經取得了足夠的字元，我們就要去更新 valid ，這個數字是看每個字元的數量是不是都足夠了。

何時要收縮窗口？

當 valid 和目標的 key 的數量一至的時候，代表我們已經湊足了所有的字元，接下來我們要去檢查看看是不是有多的資訊可以被刪掉，例如：有些字元可能是需要的，但是早就收集超過需要的數量了。

收縮窗口時，需要更新哪些資訊？

此時這個窗口的大小有沒有比之前的窗口還要小？有的話我們就要更新
新的最小窗口字串的起始點
新的最小窗口的長度
接著縮小窗口，如果說此時某字元在 memo 中的計數和目標中相同了，我們要減少 valid 的數量（也會順便結束 while）
並且把字元的計數減一

最終結果要在「擴大窗口」時更新還是「收縮窗口」時更新？
此題在「收縮」時更新

滑動窗口還會有一個特點，增大窗口跟減少窗口的行為一般來說都是相反的。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        target = Counter(list(t))
        memo = defaultdict(int)
        left = 0
        right = 0
        valid = 0
        start = 0
        L = float('inf')
        while right < len(s):
            char = s[right]
            right += 1
            if char in target:
                memo[char] += 1
                if memo[char] == target[char]:
                    valid += 1

            while valid == len(target):
                if right - left < L:
                    start = left
                    L = right - left
                remove = s[left]
                left += 1
                if remove in target:
                    if memo[remove] == target[remove]:
                        valid -= 1
                    memo[remove] -= 1

        return '' if L == float('inf') else s[start:start+L]