今天是紀錄LeetCode解題的第三天

第三題題目：Given a string s, find the length of the longest substring without duplicate characters.給定一個字串，找出最長沒有重複的子字串長度

範例：

input：s = "abcabcbb"
output：3
explanation：答案是"abc",長度為3

這題的概念非常簡單，程式碼如下

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        list_s = [] #儲存子字串
        max_len = 0 #最大的長度
        left = 0
        for right in range(len(s)):
            c = s[right]
            # 如果 c 已經在 list_s 中，從左邊移除直到沒有重複
            while c in list_s:
                list_s.pop(0)
                left += 1
            list_s.append(c)
            max_len = max(max_len, len(list_s))
        
        return max_len

以範例一說明
初始狀態

• s = "abcabcbb"
• list_s = [], max_len = 0, left = 0

第一次執行(right = 0, s[0] = 'a')

• c = 'a'
• while c in list_s → while 'a' in [] → False（不進入）
• list_s.append('a') → list_s = ['a']
• max_len = max(0, 1) → max_len = 1

第二次執行(right = 1, s[1] = 'b')

• c = 'b'
• while c in list_s → while 'b' in [] → False（不進入）
• list_s.append('b') → list_s = ['a','b']
• max_len = max(1, 2) → max_len = 2

第三次執行(right = 2, s[1] = 'c')

• c = 'c'
• while c in list_s → while 'c' in [] → False（不進入）
• list_s.append('c') → list_s = ['a','b','c']
• max_len = max(2, 3) → max_len = 3

第四次執行(right = 3, s[1] = 'a')

• c = 'a'
• while c in list_s → while 'a' in [] → True，進入 while
  • list_s.pop(0)（移除左邊）→ list_s = ['b','c']
  • left += 1 → left = 1
• 再次檢查第6行：'a' in ['b','c'] → False，跳出 while
• list_s.append('a') → list_s = ['b','c','a']
• max_len = max(3, 3) → max_len = 3

依此類推執行完畢就能夠得到子字串的最大長度了，邏輯大概就是我們在掃描字串的過程中遇到重複的字元，代表目前子字串已經不符合「無重複」的條件，就逐一把最左邊的字元刪除，直到把重複的那個字元刪掉為止，整個過程不斷向右逐一掃瞄，當沒有重複就繼續擴展，有重複就刪除修正，最後留下的最大值就是我們要找的「最長不重複子字串長度」