MediumRating 1533

3. Longest Substring Without Repeating Characters

hash-tablestringsliding-window

解題說明

Longest Substring Without Repeating Characters

題目描述：給定字串 s，找出不含重複字元的最長子字串的長度。

解題思路：滑動視窗法：維護左指標 left 和雜湊表（字元 → 最後出現索引）。右指標遍歷字串；當遇到重複字元時，將 left 移動到重複字元上次出現位置的下一個（跳過重複）。每步更新視窗最大長度。注意 left 只向右移動（不能向左縮退）。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個字元最多進出視窗各一次。

空間複雜度：O(min(n, |alphabet|)) — 雜湊表大小受字元集大小限制。

虛擬碼

1. left = 0, maxLen = 0, lastSeen = {}
2. For right from 0 to n-1:
   a. If s[right] in lastSeen and lastSeen[s[right]] >= left:
      left = lastSeen[s[right]] + 1
   b. lastSeen[s[right]] = right
   c. maxLen = max(maxLen, right - left + 1)
3. Return maxLen

其他解法

嵌套迴圈 O(n²)：對每個起點，擴展直至遇重複 — 邏輯簡單但低效。

集合逐一移除 O(n) 但常數較大：用集合而非字典，逐一從左移除直至重複消失 — 同漸近複雜度但常數不優。

延伸思考

若限制於最多 k 個不同字符？
如何回傳實際的子串而非長度？
若考慮大小寫不敏感？

Longest Substring Without Repeating Characters — CaffeCode