這是一個關于字符串的經典問題,給定一個字符串,求出其中最長的不含有重復字符的子串。例如,給定字符串 abcabcbb
,則其中最長的不含重復字符的子串為 abc
,長度為 3
。
一種解決這個問題的方法是使用滑動窗口。我們可以從字符串的開頭開始,逐個添加字符,直到出現重復字符,然后從重復字符的位置開始繼續添加字符。每次添加字符時,我們可以使用一個哈希表來存儲字符的位置,如果當前字符已經出現過,則更新哈希表中字符的位置,并更新窗口的起始位置。
具體思路如下:
當我們遍歷字符串時,可以用一個滑動窗口來維護當前不含重復字符的子串。每次添加字符時,如果該字符在窗口中已經出現過,則更新窗口的起始位置,使窗口不包含重復字符。
算法的具體步驟如下:
- 定義滑動窗口的起始位置
start
和結束位置end
,初始時start=0
和end=0
。 - 定義一個哈希表
char_index
來存儲字符在字符串中的位置。 - 定義一個變量
max_len
表示最長不含重復字符的子串的長度,初始時設為0
。 - 遍歷字符串中的每一個字符,記當前字符為
char
,當前字符在字符串中的位置為index
。 - 如果字符
char
已經在窗口中出現過,即字符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 實現的示例代碼:
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 已經在窗口中出現過,更新窗口的起始位置
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瀏覽量
9168 -
字符
+關注
關注
0文章
234瀏覽量
25416 -
字符串
+關注
關注
1文章
589瀏覽量
20933
發布評論請先 登錄
相關推薦
python3如何取出重復3次的字符串保存為3列
本文檔的主要內容詳細介紹的是python3如何取出重復3次的字符串保存為3列詳細資料免費下載C語言資料說明。
發表于 11-16 16:17
?4次下載
什么是復制字符串?Python如何復制字符串
連續幾篇文章都在寫 Python 字符串,這出乎我的意料了。但是,有的問題,不寫不行,特別是那種靈機一動想到的問題,最后你發現,很多人根本不懂卻又誤以為自己懂了。那就繼續刨根問底,探究個明白吧
發表于 11-25 10:32
?3119次閱讀
2.2 python字符串類型
2.2 python字符串類型 1. 如何定義字符串? 字符串是Python中最常用的數據類型之一。 使用單引號或雙引號來創建
python字符串有哪些特定方法
python字符串序列操作也適用于列表和元組。
python字符串還有獨有方法,即字符串對象的函數,其他對象不可調用,只有
Python字符編碼轉換
UNICODE字符串可以與任意字符編碼的字節進行相互轉換,如圖: 那么大家很容易想到一個問題,就是不同的字符編碼的字節可以通過Unicode相互轉換嗎?答案是肯定的。 Python2中

Python 如何判斷字符串是否包含子串
方法 使用 字符串 對象的 find 方法,如果有找到子串,就可以返回指定子串在字符串中的出現位置,如果沒有找到,就返回 -1 >> > "hello,
python輸出固定長度的字符串
Python 是一種強大而靈活的編程語言,具有許多用于處理字符串的功能。在 Python 中,有多種方法可以輸出固定長度的字符串。下面將詳細介紹這些方法。 方法一:使用
評論