python算法題之《給定一個(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è)子序列纤子，不是子串。
代碼及解析
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 字典用來存放當(dāng)前字母在位置（從1開始）
dic = {}
# 最大子串長度
ans = 0
# flag為標(biāo)志位款票，即當(dāng)前未重復(fù)的起始值
flag =0
for i in range(len(s)):
# 若當(dāng)前字符已經(jīng)存在于字典的鍵中
if s[i] in dic:
# 返回當(dāng)前字母對應(yīng)的位置與flag中較大值作為flag為重復(fù)起始值控硼，不讓起始值變小
flag = max(dic[s[i]],flag)
# 計(jì)算未重復(fù)的值
ans = max(i-flag+1, ans)
# 將當(dāng)前字符的位置存于字典中
dic[s[i]] = i+1
return ans
