'''
給你一個字元串 S、一個字元串 T，請在字元串 S 裡面找出：包含 T 所有字元的最小子串。
示例：
輸入: S = "ADOBECODEBANC", T = "ABC"
輸出: "BANC"
說明：
如果 S 中不存這樣的子串，則傳回空字元串 ""。
如果 S 中存在這樣的子串，我們保證它是唯一的答案。
'''
# 思路：滑動視窗适合求'連續'問題
# left, right, 如果視窗裡面不符合條件，right+1， 如果符合，收縮左邊的視窗，left+1
class Solution:
def minWindow(self, s: str, t: str) -> str:
# requires: T 的字典
# windows：視窗的字典
def is_valid(requires, windows):
for key, value in requires.items():
if windows.get(key,0) < value:
return False
return True
if not s or not t: return ''
N = len(s)
requires = {}
for item in t:
requires[item] = requires.get(item, 0) + 1
# 滑動視窗
windows = {s[0]:1}
left, right = 0, 0
ret_len, ret = N, ''
while right < N:
if is_valid(requires, windows):
if right-left+1 <= ret_len:
ret_len = right-left+1
ret = s[left: right+1]
windows[s[left]] -= 1
left += 1
else:
right += 1
if right < N: # !!!!
windows[s[right]] = windows.get(s[right], 0) + 1
return ret
方法一：滑動視窗
思路和算法
本問題要求我們傳回字元串 ss 中包含字元串 tt 的全部字元的最小視窗。我們稱包含 tt 的全部字母的視窗為「可行」視窗。
我們可以用滑動視窗的思想解決這個問題，在滑動視窗類型的問題中都會有兩個指針。一個用于「延伸」現有視窗的 rr 指針，和一個用于「收縮」視窗的 ll 指針。在任意時刻，隻有一個指針運動，而另一個保持靜止。我們在 ss 上滑動視窗，通過移動 rr 指針不斷擴張視窗。當視窗包含 tt 全部所需的字元後，如果能收縮，我們就收縮視窗直到得到最小視窗。
如何判斷目前的視窗包含所有 tt 所需的字元呢？我們可以用一個哈希表表示 tt 中所有的字元以及它們的個數，用一個哈希表動态維護視窗中所有的字元以及它們的個數，如果這個動态表中包含 tt 的哈希表中的所有字元，并且對應的個數都不小于 tt 的哈希表中各個字元的個數，那麼目前的視窗是「可行」的。
注意：這裡 tt 中可能出現重複的字元，是以我們要記錄字元的個數。
考慮如何優化？ 如果 s = XX ... ... XABCXXXX = XX ⋯ XABCXXXX， t=ABC，那麼顯然 [XX⋯XABC] 是第一個得到的「可行」區間，得到這個可行區間後，我們按照「收縮」視窗的原則更新左邊界，得到最小區間。我們其實做了一些無用的操作，就是更新右邊界的時候「延伸」進了很多無用的 X，更新左邊界的時候「收縮」扔掉了這些無用的 X，做了這麼多無用的操作，隻是為了得到短短的 ABC。沒錯，其實在 ss 中，有的字元我們是不關心的，我們隻關心 tt 中出現的字元，我們可不可以先預處理 ss，扔掉那些 tt 中沒有出現的字元，然後再做滑動視窗呢？也許你會說，這樣可能出現 XXABXXC 的情況，在統計長度的時候可以扔掉前兩個 X，但是不扔掉中間的 X，怎樣解決這個問題呢？優化後的時空複雜度又是多少？
作者：LeetCode-Solution
連結：https://leetcode-cn.com/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
如果這篇文章幫助到了你，你可以請作者喝一杯咖啡