無重複字元的最長子串 Python

來自專欄 LeetCode python Java1 人贊了文章

給定一個字元串，找出不含有重複字元的最長子串的長度。

示例：

給定 "abcabcbb" ，沒有重複字元的最長子串是 "abc" ，那麼長度就是3。

給定 "bbbbb" ，最長的子串就是 "b" ，長度是1。

給定 "pwwkew" ，最長子串是 "wke" ，長度是3。請注意答案必須是一個子串，"pwke" 是 子序列 而不是子串。

Python

class Solution: def lengthOfLongestSubstring(self,s): result = 0 l = (s) d={} i=0 j=0 while (j < len(l)): if (l[j] in d): i = max(d[l[j]] + 1,i) result = max(result,j-i+1) d[l[j]] = j j = j + 1 return result

此題難點在於聯想有一個滑塊 [ i , j ] 在字元串中，每當list[ j]存在於字典中，取得原始index i`，滑塊滑動到 [i`+1, j ] 。結果就是曾經存在的最大滑塊的長度。

這道題的簡單解法就是雙循環每一次移動i都遍歷所有的j ，從i+1 開始，一直移動到list結尾。新手可以從這個想法出發。

探索的想法是可以用鏈表形成heap解決，此方法以後補充。