---
title: "3. Longest Substring Without Repeating Characters"
url: "https://laigary.com/interview/coding/3-longest-substring-without-repeating-characters"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-25"
tags: ["Sliding Window", "Two Pointers", "Hash Table"]
---

# 3. Longest Substring Without Repeating Characters

[3\. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

給一個字串，找出**不含重複字元**的最長子字串長度。注意是「子字串」（連續）而不是「子序列」。

## 思路

這一題其實是可以透過暴力解法想辦法算出來的，那就是窮舉出所有的子字串，並且檢查每一個子字串有沒有重複的字元。時間複雜度約為 $O(n^3)$。

不過這一題的做法算是雙指針的初始練習題，要第一次寫就想到的確不容易，不過可以從這個題目練習核心的觀念。

原先的暴力窮舉法最主要是不斷的重複掃描重複的地方 —— 檢查 `s[0..5]` 的時候明明已經知道 `s[0..4]` 沒有重複了，下一輪卻又從頭數一遍。如果使用雙指針的話，就可以盡可能地減少重複掃描的動作：**右指針只前進、左指針只前進，兩個都不回頭**。

### 要用什麼記錄窗口內容

要做到這個目的，我們還需要一個方法來記錄**不重複的字元**。我一開始是想到用 `set()` 來記錄，不過這樣的話我們沒辦法知道次數，而且這個重複字元不一定是在最後一個字元。

這個轉折是關鍵：`set` 只能回答「在不在」，但收縮窗口時我要知道「**還剩幾個**」才知道什麼時候可以停。所以我想到了用 `Hash Table` 來記錄 —— 每次掃描一個字元的時候，我們就馬上檢查這個字元是不是出現兩次了，那這時候慢指針就會開始往右掃描，每次掃到一個字元，就從 `Hash Table` 上減去一個計數，直到計數只剩一次為止。

### 滑動窗口的四個問題

這題套用的就是 [Sliding Window 模板](/interview/coding/sliding-window-template) 那套框架，動手前先把四個問題答完：

| 問題 | 這題的答案 |
|---|---|
| 窗口**增大**時要更新哪些資訊？ | 計算每個字元的計數 |
| **何時**要收縮窗口？ | 當該字元的計數大於 1 |
| **收縮**時要更新哪些資訊？ | 減少該字元的計數，直到小於或等於 1 |
| 答案在「擴大」還是「收縮」時更新？ | **收縮完窗口之後** |

最後一個問題最容易錯。這題求的是**最長**，所以要等窗口重新變成合法的（沒有重複）才能取 `max` —— 收縮的過程中窗口是不合法的，那時候的長度不能算。反過來如果題目求**最短**（例如 [76. Minimum Window Substring](/interview/coding/76-minimum-window-substring)），就要在收縮的**每一步**都更新答案，因為越縮越短。

## 解題方向

### 暴力解

```python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        def check(start, end):
            chars = defaultdict(int)
            for i in range(start, end + 1):
                c = s[i]
                chars[c] += 1
                if chars[c] > 1:
                    return False
            return True

        n = len(s)

        res = 0
        for start in range(n):
            for end in range(start, n):
                if check(start, end):
                    res = max(res, end - start + 1)
        return res
```

### 滑動窗口

```python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 0
        res = 0
        visited = defaultdict(int)

        while right < len(s):
            char = s[right]
            right += 1
            visited[char] += 1

            while visited[char] > 1:
                d = s[left]
                left += 1
                visited[d] -= 1
            res = max(res, right - left)

        return res
```

有一個地方很容易搞混：**`right += 1` 是在讀完字元之後馬上做的**，所以進到 `res = max(...)` 那一行時，`right` 已經指向「窗口外的下一格」。於是窗口是左閉右開的 `[left, right)`，長度就是 `right - left`，**不是 `right - left + 1`**。

如果改成 `for right in range(len(s))` 的寫法（模板裡是這樣），`right` 就還在窗口內，長度才要 `+1`。兩種都對，但混用就會差一。

內層 `while` 只需要檢查 `visited[char]`（剛進來的那個字元），不用檢查整個窗口 —— 因為窗口在這個字元進來之前是合法的，唯一可能的重複就是它。

## 補充

**同一個「求最長」的骨架**：[424. Longest Repeating Character Replacement](/interview/coding/424-longest-repeating-character-replacement)（窗口條件換成「可替換次數不超過 k」）、[1004. Max Consecutive Ones III](/interview/coding/1004-max-consecutive-ones-iii)（窗口裡的 0 不超過 k 個）。

**求最短的對照**：[76. Minimum Window Substring](/interview/coding/76-minimum-window-substring)、[209. Minimum Size Subarray Sum](/interview/coding/209-minimum-size-subarray-sum)。骨架一樣，差別只在答案更新的時機，見 [Sliding Window 模板](/interview/coding/sliding-window-template)。

## 複雜度

**暴力解**
- 時間 $O(n^3)$ — $O(n^2)$ 個子字串，每個再花 $O(n)$ 檢查有沒有重複
- 空間 $O(\min(n, |\Sigma|))$ — `check` 裡的計數表

**滑動窗口**
- 時間 $O(n)$ — `left` 和 `right` 都只單向前進，各走一趟；內層 `while` 的總執行次數也是 $O(n)$，不是每次都 $O(n)$
- 空間 $O(\min(n, |\Sigma|))$ — 窗口裡最多裝下字元集大小那麼多種字元

其中 $n$ 是字串長度、$|\Sigma|$ 是字元集大小（只有小寫英文就是 26）。**內層迴圈不會讓時間變成 $O(n^2)$** —— 因為 `left` 從頭到尾只走過一遍，所有收縮加起來也只有 $n$ 步。