---
title: "567. Permutation in String"
url: "https://laigary.com/interview/coding/567-permutation-in-string"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-08-02"
tags: ["Two Pointers"]
---

# 567. Permutation in String

[567. Permutation in String](https://leetcode.com/problems/permutation-in-string/)

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

## 思路

### 自問自答的順序

[滑動窗口](/interview/coding/sliding-window-template)的題目，我是照這串問題往下填的：

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

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

### `valid` 是一個快取

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

```text
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 點的答案。

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

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

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

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

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

## 解題方向

### while 版

```python
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`。

```python
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
```

## 補充

### 收縮那兩行寫反會怎樣

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

```text
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)$