LeetCode 筆記 - 3. Longest Substring Without Repeating Characters

題目在此 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

也許你也會想看看