題目敘述

給定一個字串 s，請找出其中不包含重複字元的最長子字串的長度。

解題思路

這題的標籤包含：

• Hash Table
• String
• Sliding Window

其中最關鍵的是 Sliding Window 這個技巧。

什麼是 Sliding Window？

Sliding Window 是一種常用於字串或陣列的技巧，透過維持一個「開口與關口」來動態追蹤某個子陣列或子字串的狀態。就像開關窗簾一樣，視窗會根據條件不斷左右移動。

在本題中，我們的目標是找出沒有重複字元的子字串，並隨時記錄下目前出現過的字元。每當遇到重複字元時，就「關窗」也就是將左邊界往右推，排除掉重複的那個字元。

為什麼要用 Hash Table？

因為我們需要即時知道每個字元上一次出現的位置，以便在滑動視窗的過程中快速判斷是否發生重複。Hash Table（字典）能以 $O(1)$ 的時間找到某個字元是否出現過以及其對應的索引。

範例說明（以字串 "app" 為例）

「app」的所有子字串如下：

• a
• p
• p（這是重複字元）
• ap
• pp（包含重複）
• app（包含重複）

觀察可得，最長的、不含重複字元的子字串是 "ap"，長度為 2。

這也說明了為什麼我們需要隨時記住已出現過的字元，以便一旦遇到重複，就要移動視窗的左界，排除重複的部分。

程式碼實作

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start_index = -1  # 視窗左邊界
        max_len = 0       # 最長長度記錄
        char_index = {}  # 最後一次出現的索引

        for i, ch in enumerate(s):
            if ch in char_index and char_index[ch] > start_index:
                # 如果當前字元重複，並且出現在視窗內，移動左邊界
                start_index = char_index[ch]
            max_len = max(max_len, i - start_index)
            char_index[ch] = i  # 記錄最新出現位置

        return max_len

程式比較需要注意的是以下兩點：

首先是start_index = -1 是為了讓子字串長度可以簡單地用 i - start_index 表示，從第 0 個字元開始計算時不需額外調整。
還有就是char_index[ch] > start_index 確保 start_index 只有在 char_index[ch] 有大於目前 start_index 時才被更新，確保視窗左邊界都有符合題目規範，視窗只會有不重複子字串

時間與空間複雜度分析

• 時間複雜度（Time Complexity）：$O(n)$
  每個字元最多被存取兩次（進入與移除視窗）。

• 空間複雜度（Space Complexity）：$O(m)$
  其中 $m$ 是字元種類的總數（對於英文字母最多是 26～128 個）。