➣ Reading Time: 6 minutes

題目出處

https://leetcode.com/problems/longest-substring-without-repeating-characters/

難度

Medium

題目分類

HashTable, TwoPointers, String, SlidingWindow

個人手繪解法筆記 (解法重點)

sliding window

正如其名,移動的窗戶,也就是表示在 window 範圍內必須符合我們要的答案。

two pointers

我們建立兩個指標 l,r,
r 是正常的向前搜尋,
l 是當目前 l,r 所框出的 window 範圍出現不符合題目要求時,「反覆」移動 l 直到 window 符合題目要求。

示意圖:(r先跑,l依照條件變化而跑)

示意圖:(l依照條件變化而跑,為了符合條件)

我們可以發現當下長度 = (r-l) + 1

HashTable

示意圖:(用 Queue 來儲存已存在的 window 中的字)

在搜尋目前 window 是否符合條件時,我們需要建立一個 HashTable,幫助我們速查特定值是否存在表裡面,
我們建立的 HashTable 也需要達到 Queue 的功能 (因為隨著 l 的移動,會有先進先出的問題),
我們可以看到,當 b 進來時,我們必須一直丟到 Queue 裡面沒有 b 為止,「才是正確的 window 」

個人範例程式碼

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        if len(s) == 0:
            ans = 0
        else:
            ans = 0
            queue_list = []
            l = 0 # left pointer

            for r in range(len(s)): # s[r], get one new word
                # found duplicate in sliding window, remove until duplicate not found
                while s[r] in queue_list: 
                    queue_list.pop(0)
                    l += 1
                # not found or all duplicate removed, push new word s[r]
                queue_list.append(s[r]) 
                # update answer
                ans = max(ans, r-l+1)     
        return ans

Reference

https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1134357/O(n)-Time-and-Space-Sliding-Window

⭐Python leetcode 相關文章整理⭐:
⭐Leetcode 解題紀錄⭐:難度Tag
⭐面試最經典 Top 75 題⭐:
1.【Leetcode】python - [1] Two Sum 兩數之和 個人手繪解法筆記 (只講解法重點, 內含範例程式碼)#Easy#Array #HashTable
3.【Leetcode】python - [3] Longest Substring Without Repeating Characters 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#HashTable #TwoPointers #String #SlidingWindow
5.【Leetcode】python - [5] Longest Palindromic Substring 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#String #DP
11.【Leetcode】python - [11] Container With Most Water 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#Array #TwoPointers
15.【Leetcode】python - [15] 3Sum 三數之和 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#Array #TwoPointers
48.【Leetcode】python - [48] Rotate Image 旋轉矩陣 個人手繪解法筆記與解題思考建議 (只講解法重點, 內含範例程式碼)#Medium (但我覺得很難)#Array
104.【Leetcode】python - [104] Maximum Depth of Binary Tree 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Easy#Tree #DFS #Recursion
⭐Leetcode 小技巧⭐:
1.【Python】python 測試程式 – 利用 doctest 測試 python testcase 的優雅寫法,適用於 leetcode (doctest in function,搭配 function 的用法)
2.【Leetcode】python – 利用 doctest 測試 leetcode python testcase 的優雅寫法 (doctest in class,搭配 class 的用法)
⭐【喜歡我的文章嗎? 幫忙按讚除了鼓勵外,我也會將部分所得捐出!
如果喜歡我的文章,請幫我在下方【按五下Like】 (Google, Facebook 免費註冊),會由 「LikeCoin」 贊助作者鼓勵繼續創作,扣除掉網站本身經營的成本 (可惜目前還是虧本的),我會將 【50% 收益全部捐出】 並公開發文,讀者們「只需幫忙按讚,完全不用出錢」哦!

likecoin-steps