Python版LeetCode3. 無重複字元的最長子串

本文轉載自【微信公眾號：機器學習演算法與Python精研，ID：AITop100】經微信公眾號授權轉載，如需轉載與原文作者聯絡

題目：

給定一個字串，找出不含有重複字元的

最長子串

的長度。

示例：

給定

“abcabcbb”

，沒有重複字元的最長子串是

“abc”

，那麼長度就是3。

給定

“bbbbb”

，最長的子串就是

“b”

，長度是1。

給定

“pwwkew”

，最長子串是

“wke”

，長度是3。請注意答案必須是一個

子串

，

“pwke”

是 而不是子串。

思路：

採用切分的方式，遇到重複字元時，記錄無重複字元的長度，把前面的所有字串“丟掉”然後以這個起點重新開始做切分，再遇到相同字元得到的長度與前面對比，取最大值，往復的到。

參考程式碼：

class

Solution

：

def

lengthOfLongestSubstring

（self， s）

：

“”“

：type s： str

：rtype： int

”“”

d = {}

start =

0

ans =

0

for

i，c

in

enumerate（s）：

if

c

in

d：

start = max（start， d［c］ +

1

）

d［c］ = i

ans = max（ans， i - start +

1

）

return

ans