原題目
給定一個(gè)字符串乌叶，找出不含有重復(fù)字符的最長子串的長度。
示例：
給定 "abcabcbb" ，沒有重復(fù)字符的最長子串是 "abc" ，那么長度就是
給定 "bbbbb" 肩榕，最長的子串就是 "b" ，長度是1。
給定 "pwwkew" 株汉，最長子串是 "wke" 筐乳，長度是3。請注意答案必須是一個(gè)子串乔妈，"pwke" 是 子序列 而不是子串蝙云。
思路
leetcode 不但要求算法正確 而且對算法有速度要求，因此這里不討論暴力算法
- 用一個(gè)字典保存在遍歷時(shí)字符串中字符出現(xiàn)的最后位置
- 用快慢指針標(biāo)記不重復(fù)子串的開始和結(jié)束路召，開始搜索時(shí)勃刨，慢指針i=0，標(biāo)記子串開始股淡，快指針j標(biāo)記子串結(jié)束
- 移動(dòng)j時(shí)身隐，首先檢測當(dāng)前字符是否已經(jīng)在字典中存有索引，如有檢測到已經(jīng)保存有索引并且索引值大于等于子串的起始位置I 則表明移動(dòng)j時(shí)i和j之間出現(xiàn)了重復(fù)字符唯灵，此時(shí)對比子串長度贾铝，并保留大的子串長度。同時(shí)埠帕，將字串起始位置移動(dòng)到當(dāng)前字符上一次出現(xiàn)的位置之后
- 每次循環(huán)最后更新字典中當(dāng)前字符的索引值5 注意垢揩，循環(huán)結(jié)束后，j移出當(dāng)前字符串敛瓷，需要計(jì)算這最后一個(gè)不重復(fù)子串的長度
111.png
如上圖所示：當(dāng)檢測到第二個(gè)b的出現(xiàn)位置時(shí)水孩，第一個(gè)子串搜索結(jié)束，子串頭指針移動(dòng)到第一個(gè)b之后
代碼
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
i = 0
maxlen = 1
strslen = len(s)
if strslen == 0:
return 0
j = i + 1
dict1 = {}
dict1[s[i]] = i
index = -1
while j < strslen:
index = dict1.get(s[j],-1) #get this char's last found index, otherwise -1
if index != -1 and index >= i: #this char has been saved in dict and its index larger than i
maxlen = maxlen if maxlen > j -i else j-i #update maxlen
i=index + 1 # move the start pointer i after the char's first occurence
dict1[s[j]] = j #update char's latest index
j += 1 # move j
maxlen = maxlen if maxlen > j -i else j-i #after j move out of string, update maxlen again
return maxlen
