題目說明

LeetCode 3. Longest Substring Without Repeating Characters
給一個字串 s，請找出 不含重複字元的最長子字串 的長度。

範例

Input: "abcabcbb"
Output: 3
解釋：最長的不重複子字串是 "abc"，長度 3

Input: "bbbbb"
Output: 1
解釋：最長的不重複子字串是 "b"

Input: "pwwkew"
Output: 3
解釋：最長的不重複子字串是 "wke"

程式碼

Python 解法（滑動窗口）

def lengthOfLongestSubstring(s):
char_index = {}
left = 0
max_len = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1 # 移動左指標，跳過重複字元
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len

Java 解法（滑動窗口）

import java.util.*;
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> charIndex = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
left = charIndex.get(c) + 1;
}
charIndex.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}

Java vs Python 差異
• Python 用 enumerate() 同時取得索引與字元，Java 用 for 迴圈 + charAt
• Python 字典用 in 判斷，Java 用 containsKey()
• 核心邏輯都是滑動窗口：維護左、右指標，遇到重複字元就更新左指標

複雜度分析
• 時間複雜度：O(n)，每個字元最多進入或退出一次滑動窗口
• 空間複雜度：O(k)，需要額外的字典/HashMap，k 為字母種類數