題目描述：
給定一個(gè)字符串饺蔑，請你找出其中不含有重復(fù)字符的 最長子串 的長度败砂。
- 示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"馍刮，所以其長度為 3徊件。 - 示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"梭依，所以其長度為 1卖擅。 - 示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "wke"鸣奔，所以其長度為 3。
請注意惩阶，你的答案必須是 子串 的長度挎狸，"pwke" 是一個(gè)子序列，不是子串断楷。
解題思路：
最初的思路是采用笨辦法锨匆，也就是暴力的列出所有子串，判斷各個(gè)子串是否滿足“不含重復(fù)字符”的條件冬筒，如果滿足則記錄字符串長度恐锣。從最長的子串開始搜索，一旦出現(xiàn)滿足條件的子串舞痰，就返回結(jié)果土榴。
采用以上方法的時(shí)間復(fù)雜度為O(n^3)，最終在某些測試樣例上運(yùn)行超時(shí)响牛。借鑒其它的思路玷禽，可以只遍歷一次字符串的各個(gè)字符，記錄當(dāng)前最長子串的長度娃善，同時(shí)記錄當(dāng)前子串的起始位置论衍，遍歷完成后即可得最終結(jié)果。使用這種方法時(shí)聚磺，不僅要用到各個(gè)字符的value坯台，還需要用到對(duì)應(yīng)的index，充分用到所有相關(guān)信息瘫寝。時(shí)間復(fù)雜度為O(n)蜒蕾。
笨辦法：
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
n=len(s)
if n==0:
return 0
for l in range(n,0,-1):
for i in range(0,n-l+1,1):
d={}
for j in s[i:i+l]:
if d.get(j):
d[j]+=1
else:
d[j]=1
if max(d.values())==1:
return l
更快速的方法：
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start=0#當(dāng)前子串的起始位置
lmax=0#當(dāng)前最大的子串長度
d={}#用于記錄value和index之間的映射
for i,v in enumerate(s):
# v in d表示此前出現(xiàn)過相同的字符，需要重新指定start
if v in d:
start=max(d[v]+1,start)
# 記錄當(dāng)前各個(gè)字符對(duì)應(yīng)的最大index
d[v]=i
# 得到當(dāng)前最大的子串長度
lmax=max(lmax,i-start+1)
return lmax
