Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
Solution1
此方法容易想到岳服，遍歷整個字符串，子串用兩層的嵌套循環(huán)來滑動歹啼；
一旦饺鹃，子串被check出有重復的字符剩盒，切到下一個子串進行check丁存。
其中兔朦，子串的最大值用一個變量來保存，此變量每次都跟當前check的子串的長度compare
其中摇零，查重用到了set(hash查找效率快)
注意： 此算法的復雜度非常高推掸，O(n3)
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
maxl = 0
for i in range(len(s)):
for j in range(i, len(s) + 1):
if self.unique(s[i:j]):
maxl = max(maxl, j - i)
else:
break
return maxl
def unique(self, astr):
aset = set()
for s in astr:
if s not in aset:
aset.add(s)
else:
return False
return True
solution2
同樣是遍歷整個字串，但是會將每個字符都按照順序放在一個map中驻仅。
一旦check到某個字符曾經(jīng)在map中出現(xiàn)于pos谅畅，子串的長度則從pos + 1開始重新計算。
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
amap = {}
start = maxl = 0
for i in range(len(s)):
#print start, amap
if s[i] in amap and start <= amap[s[i]]:
start = amap[s[i]] + 1
else:
maxl = max(maxl, i - start + 1)
amap[s[i]] = i
return maxl
注意： 以上的算法噪服，start <= amap[s[i]]一定不能夠漏掉毡泻。不然start就會回退。
此算法粘优，只遍歷一次字符串仇味，search的動作使用到map，因此算法的復雜度為O(n)
