567. Permutation in String

──────────────────────────────────────────────────────────────────────

567. Permutation in String

給兩個字串 s1 和 s2，問 s2 裡面有沒有一段連續子字串剛好是 s1 的排列。

思路

自問自答的順序

滑動窗口的題目，我是照這串問題往下填的：

1. 我們需要想的是窗口增大的時候，需要更新哪些資訊？
2. 如果 char 在目標內，增加計數
3. 如果 char 的計數已經達到目標的計數，valid 加一
4. 何時要收縮窗口？
5. 如果窗口的字串的長度已經大於目標的字串（因為我們要找的是 permutation)
6. 收縮窗口時，需要更新哪些資訊？
7. 檢查左邊的指針的字元在目標內
8. 如果 char 的計數已經達到目標的計數，valid 減一
9. 如果 char 在目標內，減少
10. 最終結果要在「擴大窗口」時更新還是「收縮窗口」時更新？
11. 如果 valid 剛好和 target 的長度一樣的時候，代表找到 permutation 了，回傳 True

下面三節是這串問題背後的理由 —— 忘記的時候看這裡，不要硬背步驟。

valid 是一個快取

真正想問的是「現在這個窗口，是不是剛好就是 s1 的排列？」最直接的寫法是每次都比字典：

if visited == target:      # 每次 O(k)，k 是相異字元數

但窗口會滑 n 次，每次重比一輪就是 $O(n\times k)$。valid 把這個比較攤提成 $O(1)$：

valid = 目前有幾個字元的 visited 計數恰好等於 target

只要維持這個定義，valid == len(target) 就等價於「所有種類都湊齊了」。

兩個容易搞混的地方：

• valid 數的是「種類」不是「個數」，所以拿去比的是 len(target)（相異字元數），不是 len(s1)。
• 超過目標不會讓 valid 增加。 s1 = "ab"、窗口是 "aa" 時，visited['a'] 從 1 變 2，2 != 1，所以 valid 停在 1 —— 「湊齊」指的是剛好等於，多了不算。

為什麼窗口長度卡在 len(s1)

因為排列的長度是固定的。s1 的任何排列都剛好 len(s1) 個字元，所以只有長度正好等於 len(s1) 的窗口值得檢查：比它短的不可能湊齊，比它長的一定多了東西。

這題其實是固定長度的窗口，只是套了通用的可變長度模板。

right 已經先 += 1，所以窗口是 [left, right)、長度就是 right - left。長度一碰到 len(s1) 就沒有再長的理由，直接收縮。

也因為窗口長度剛好等於 len(s1) 的那一刻只出現在收縮迴圈的開頭，檢查答案就放在那一行 —— 這就是第 10 點的答案。

進場和出場的順序剛好相反

擴大和收縮是鏡像的，順序不一樣：

擴大：先加，再判斷            收縮：先判斷，再減
    visited[char] += 1            if visited[char] == target[char]:
    if visited[char] == ...:          valid -= 1
        valid += 1                visited[char] -= 1

因為 valid 記的是「現在剛好等於」，要抓的是跨越那條線的瞬間：

• 加入之後才有可能達到相等 → 先加再判斷
• 移除之前還相等，移除之後就破了 → 先判斷再減

解題方向

while 版

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        target = Counter(list(s1))
        visited = defaultdict(int)
        left = 0
        right = 0
        valid = 0
        while right < len(s2):
            char = s2[right]
            right += 1
            if char in target:
                visited[char] += 1
                if visited[char] == target[char]:
                    valid += 1
            while right - left >= len(s1):
                if valid == len(target):
                    return True
                char = s2[left]
                left += 1
                if char in target:
                    if visited[char] == target[char]:
                        valid -= 1
                    visited[char] -= 1
        return False

for 版

同一套邏輯，只是把外層換成 for，窗口長度寫成 fast - slow + 1。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        
        target = Counter(s1)
        visited = defaultdict(int)
        valid = 0

        slow = 0
        for fast in range(len(s2)):
            c2 = s2[fast]
            if c2 in target:
                visited[c2] += 1
                if visited[c2] == target[c2]:
                    valid += 1
            while fast - slow + 1 >= len(s1):
                if valid == len(target):
                    return True
                char = s2[slow]
                slow += 1
                if char in target:
                    if visited[char] == target[char]:
                        valid -= 1
                    visited[char] -= 1

        return False

補充

收縮那兩行寫反會怎樣

如果寫成「先減再判斷」：

visited[char] -= 1
if visited[char] == target[char]:   # 減完之後是 target - 1，永遠不會相等
    valid -= 1

valid 就變成只增不減 —— 窗口早就滑過去了，它還記著舊帳，於是回報一堆假的 True。20000 組隨機測資裡錯了 1803 組，最小的例子是 s1 = "bcaa"、s2 = "bababbac"：寫反回傳 True，正解是 False。

>= 其實永遠是 ==

while right - left >= len(s1) 裡的 >=，在這份程式碼裡永遠只會是 ==。內層迴圈會一直縮到 right - left < len(s1) 才出來，外層每輪只讓右邊前進一格，所以最多剛好碰到。實測 38472 個檢查點，> 一次都沒發生過。

寫 >= 只是通用模板的習慣，比較保險而已。

複雜度

設 $n$ 是 s2 的長度、$k$ 是 s1 的相異字元數。

• 時間 $O(n)$ — 每個字元最多進窗口一次、出窗口一次，而 valid 讓「湊齊了沒」的檢查是 $O(1)$。沒有 valid 的話會退化成 $O(n\times k)$
• 空間 $O(k)$ — target 和 visited 兩個字典；只有小寫英文字母時 $k\le 26$，可以視為 $O(1)$