LeetCode 解題筆記：3. Longest Substring Without Repeating Characters

作者：王一哲
日期：2026年7月10日


LeetCode 題目連結：3. Longest Substring Without Repeating Characters

解題想法

中等難度題。題目給一個字串 $s$，假設字串長度為 $n$，要找出 $s$ 之中字母不重複的連續子字串最大長度。這題可以用滑動視窗解題，用一個字典 $cnt$ 記錄視窗範圍內各字母出現的次數，用一個 for 迴圈更新視窗右端點 $right$，範圍為 $0$ 到 $n-1$，$cnt[s[right]] += 1$；再用一層 while 迴圈，當 $left \leq right$ 且 $cnt[s[left]] > 1$ 時，將 $cnt[s[left]] -= 1$、$left += 1$；跑完 while 迴圈之後，視窗範圍內已經沒有重複的字母，更新最大長度，取原來的最大長度 $imax$ 與目前的視窗長度 $right - left + 1$ 較大者。

Python 程式碼

Runtime: 18 ms, beats 23.75%. Memory: 19.25 MB, beats 68.10%.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cnt = defaultdict(int)  # 目前範圍內出現的字母
        imax = 0  # 最大長度
        left = 0  # 視窗左端點
        n = len(s)  # 字串長度
        for right in range(n):  # 掃過字串
            cnt[s[right]] += 1  # 右端新增的字母數量加 1
            # 左端點向右移，直到 s[right] 數量等於 1 為止
            while left <= right and cnt[s[right]] > 1:
                cnt[s[left]] -= 1
                left += 1
            imax = max(imax, right - left + 1)  # 更新 imax
        return imax

C++ 程式碼

Runtime: 11 ms, beats 47.95%. Memory: 11.65 MB, beats 76.88%.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> cnt;  // 目前範圍內出現的字母
        int imax = 0, left = 0, n = (int)s.size();  // 最大長度，視窗左端點，字串長度
        for(int right = 0; right < n; right++) {  // 掃過字串
            cnt[s[right]]++;  // 右端新增的字母數量加 1
            // 左端點向右移，直到 s[right] 數量等於 1 為止
            while(left <= right && cnt[s[right]] > 1) {
                cnt[s[left]]--;
                left++;
            }
            imax = max(imax, right - left + 1);  // 更新 imax
        }
        return imax;
    }
};