LeetCode 筆記 - 3. Longest Substring Without Repeating Characters

Posted on

題目在此 3. Longest Substring Without Repeating Characters

給定一個字串，請給出最長不重複子字串的長度

解題思維

這題的思維是維持一個你目前字串的 value : index 的 map
除了可以用 map 檢查是否有重複字元也可以讓下一個字串的 start 移動的更有效率

見下圖

1
2
3
4
5
  start
  v
h j z a b c a h i j g v .......
            ^
            index

當 index 遇到 a，而目前字串已經有 a
所以下一次的 start 可以直接從舊有的 a index + 1 開始檢查

Time complexity: O(n)

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        if not s:
            return 0
        
        l = len(s)
        
        index_map = {}
        max_length = start = 0
        
        for i in range(l):
            # condition 1: 新字元在 map 裡
            # condition 2: 新字元的 index 大於 start 表示在目前字串已經有新字元了
            if s[i] in index_map and start <= index_map[s[i]]:
                start = index_map[s[i]] + 1
            else:
                max_length = max(max_length, i - start + 1)
                
            index_map[s[i]] = i
            
        return max_length

也許你也會想看看