【Leetcode 筆記】 3. Longest Substring Without Repeating Characters

題目解釋

給定一個字串 s，求最長且沒有重複 character 的 substring。

範例

• 輸入: s = "abcabcbb"
• 輸出: 3

輸出是 3，因為最長的 substring 是 "abc"。

最佳解法

步驟

整段題目最重要的 pseudo code 長的像這樣：

start_char, end_char = s[left], s[right]

if end_char in substring:
    substring.revome(start_char)
    left += 1
else:
    substring.add(end_char)

如果 end_char 出現在了我們維護 substring 的 set 裡的話，我們就把 start_char 移出 set 裡面。

Q: 為什麼要這樣做呢？
A: 因為我們沒辦法確認後面的 string 還有多長！

• 主角是 right，它負責 traverse 整條 string
• 配角是 left，透過它來控制 window 的長度

除了這兩個 ptr 之外，我們還需要存 substring 的 set 以及記錄用的變數: max_sub_len，因為最後 traverse 完時，set 裡面會是最新鮮的 substring 而非最長的 substring。

NOTE: left 跟 right 中間的那段就是所謂的滑動窗口 (silding window)。

程式碼

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        substring = set()
        max_sub_len = 0

        for right in range(len(s)):
            while s[right] in substring:
                substring.remove(s[left])
                left += 1
            else:
                substring.add(s[right])
            max_sub_len = max(len(substring), max_sub_len)

        return max_sub_len

時間複雜度

O(n)，n 是 s 的字串個數。

空間複雜度

O(n)。

結語

很順的把 if...else 中的 if 換成 while 後才發現…
python 的 while 居然可以搭配 else (已知用火🔥) ！！！

因為像 C/C++ 就不行，蛇蛇是真的直覺 🐍。

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26