這是一個關于字符串的經(jīng)典問題,給定一個字符串,求出其中最長的不含有重復字符的子串。例如,給定字符串 abcabcbb
,則其中最長的不含重復字符的子串為 abc
,長度為 3
。
一種解決這個問題的方法是使用滑動窗口。我們可以從字符串的開頭開始,逐個添加字符,直到出現(xiàn)重復字符,然后從重復字符的位置開始繼續(xù)添加字符。每次添加字符時,我們可以使用一個哈希表來存儲字符的位置,如果當前字符已經(jīng)出現(xiàn)過,則更新哈希表中字符的位置,并更新窗口的起始位置。
具體思路如下:
當我們遍歷字符串時,可以用一個滑動窗口來維護當前不含重復字符的子串。每次添加字符時,如果該字符在窗口中已經(jīng)出現(xiàn)過,則更新窗口的起始位置,使窗口不包含重復字符。
算法的具體步驟如下:
- 定義滑動窗口的起始位置
start
和結束位置end
,初始時start=0
和end=0
。 - 定義一個哈希表
char_index
來存儲字符在字符串中的位置。 - 定義一個變量
max_len
表示最長不含重復字符的子串的長度,初始時設為0
。 - 遍歷字符串中的每一個字符,記當前字符為
char
,當前字符在字符串中的位置為index
。 - 如果字符
char
已經(jīng)在窗口中出現(xiàn)過,即字符char
在哈希表char_index
中對應的值不為0
,并且該值大于等于窗口的起始位置start
,則更新窗口的起始位置start
為char_index[char] + 1
。 - 更新窗口的結束位置
end
為index
,并更新哈希表char_index
中字符char
對應的值為index
。 - 更新最長不含重復字符的子串的長度
max_len
,即max_len = max(max_len, end - start + 1)
。 - 重復步驟 4-7,直到遍歷完整個字符串。
- 返回最長不含重復字符的子串的長度
max_len
。
以下是一個用 Python 實現(xiàn)的示例代碼:
def length_of_longest_substring(s: str) -> int:
# 定義窗口的起始位置和結束位置
start: int = 0
end: int = 0
# 定義一個哈希表存儲字符的位置
char_index: dict = {}
# 最長不含重復字符的子串的長度
max_len: int = 0
# 遍歷字符串
for index, char in enumerate(s):
# 如果字符 char 已經(jīng)在窗口中出現(xiàn)過,更新窗口的起始位置
if char in char_index and char_index[char] >= start:
start = char_index[char] + 1
# 更新窗口的結束位置和窗口中字符 char 的位置
end = index
char_index[char] = index
# 更新最長不含重復字符的子串的長度
max_len = max(max_len, end - start + 1)
return max_len
使用該算法,我們可以輸入字符串 abcabcbb
,得到最長不含重復字符的子串的長度 3
,即為題目中給出的示例的答案。
-
ABC
+關注
關注
0文章
12瀏覽量
8899 -
字符
+關注
關注
0文章
233瀏覽量
25199 -
字符串
+關注
關注
1文章
578瀏覽量
20506
發(fā)布評論請先 登錄
相關推薦
評論