[036] LeetCode 76演算法【Minimum Window Substring】最小窗口子字串

76. Minimum Window Substring(Hard)

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

這一題很好玩，他是要在S字串裡面，找出最短字串且該字串包含T的字串長度組合，題目有限制複雜度不能超過O(n)，既然都要跑迴圈了，那我們就第一次把S出現的值記錄下來就可以，後面再去想要怎麼解決這題。

首先我們把題目縮短一點看好了

Input: S = "ABANC", T = "ABC"
Output: "BANC"

第一次去查找S的第一個字串的時候發現T也會有，此時就添加A

第二次B也有，此時添加B變成AB

第三次的時候發現A重複了，此時添加A並且刪去第一個A成為BA

第四次N沒有出現，繼續動作，此時微BAN

第五次最後一個條件C出現了，答案就是BANC

從上面來看會發現他很像一條貪食蛇在慢慢前進，只是他並不會越吃越長，他會在吃到特定的東西變短，也有人覺得很像是窗戶，好像在移動一個大行窗戶，這個算法其實有一個專有名詞叫做slide window，是網路TCP協議的通用算法，大家常常在用的Socket就是從TCP封裝上來的。

這種題目難的地方在於，你知道怎麼寫了，可是要你一次寫出bug free的代碼確實有點難度，主要是細節太多要判斷了，我們直接實做吧。

如果不懂這個算法精隨，這邊可以看到圖形解法。