題目出處

76. Minimum Window Substring

難度

hard

個人範例程式碼 – two pointer + sliding window

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s:
            return s

        counter_t = Counter(t)

        ans = ""
        fast = 0
        queue = []
        valid_num = 0

        window_counter = defaultdict(int)
        for slow, c in enumerate(s):
            while fast < len(s) and not self.is_sub_counter(window_counter, counter_t): # correct: collections <= set(queue)
                # print(slow, fast, window_counter)
                window_counter[s[fast]] += 1
                queue.append(s[fast])
                fast += 1
            else: # window matches collection words
                if self.is_sub_counter(window_counter, counter_t):
                    ans = s[slow:fast] if ans == "" or len(s[slow:fast]) <= len(ans) else ans
            # remove start until set not match
            c = queue.pop(0)
            window_counter[c] -= 1

        return ans

    def is_sub_counter(self, counter_s, counter_t):
        # print(counter_s, counter_t)
        for key, value in counter_t.items():
            if key not in counter_s:
                return False
            if counter_s[key] < value: # "a", "aa" = 1 < 2, must >= 2
                return False
        return True

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

這題最麻煩的部分是在 counter 跟 is sub counter 的關係，
如果這題單純只有設計成要找 set() 的樣子會簡單很多，

例如：ABC 找 ABC 用 set() 很容易，
但要比較 AABC 與 AABC 沒辦法用 set() 的方法，因此我們需要另外寫一個方法 is_sub_counter()

input handling

如果沒有 s，回傳 s

Boundary conditions

利用同向 two pointer: slow, fast 控制搜尋範圍。

• fast：替我們決定 sliding window 的結束位置
• slow：替我們決定 sliding window

個人範例程式碼 – two pointer + sliding window 優化版

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s:
            return s

        counter_t = Counter(t)

        ans = ""
        fast = 0
        queue = []
        valid = 0

        window_counter = defaultdict(int)
        for slow, c in enumerate(s):
            # print(slow, fast, valid, window_counter, ans)
            while fast < len(s) and valid < len(t): # correct: collections <= set(queue)
                # print(slow, fast, valid, window_counter, ans)
                key = s[fast]
                if key in counter_t:  
                    window_counter[key] += 1
                    if window_counter[key] <= counter_t[key]:
                        valid += 1
                fast += 1
            else: # window matches collection words
                if valid == len(t):
                    ans = s[slow:fast] if ans == "" or len(s[slow:fast]) <= len(ans) else ans

            # remove start until set not match
            if c in counter_t:
                window_counter[c] -= 1
                if window_counter[c] < counter_t[c]:
                    valid -= 1

        return ans

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

上面的作法其實沒什麼問題，速度慢的原因「最主要是在調用 is_sub_counter() 這個 function 太多次」，
然而，我們稍微計算一下就能知道，每次我們使用 is_sub_counter()，我們都需要花 O(N) 的時間去計算 (for counter_t)，
但這個動作其實是可以邊在我們 sliding window 的過程中順便記憶的，這樣就可以避免掉每一次重複的比對

def is_sub_counter(self, counter_s, counter_t):
    # print(counter_s, counter_t)
    for key, value in counter_t.items():
        if key not in counter_s:
            return False
        if counter_s[key] < value: # "a", "aa" = 1 < 2, must >= 2
            return False
    return True

因此在新的概念中，我們設計了一個數字 valid，
幫助我們記憶前面的 sliding window 中，現在有 valid 的數量，

我們在設計時比較兩個 counter 紀錄，只有在範圍比較小的時候紀錄有 valid，
而當「重複數字」我們不記在 valid，但 counter 仍要記錄，
「 因為在 sliding 的過程中有可能會砍掉重複的，但依然保持 valid 」

input handling

如果沒有 s，回傳 s

Boundary conditions

利用同向 two pointer: slow, fast 控制搜尋範圍。

• fast：替我們決定 sliding window 的結束位置
• slow：替我們決定 sliding window

Reference

• 最小子串覆盖 · Minimum Window Substring