Longest Substring Without Repeating Characters問(wèn)題：求給定字符串的最大無(wú)重復(fù)字符的子串的長(zhǎng)度干像。
難度：中等
思路：用2個(gè)變量（start, end）分別保存子串的起點(diǎn)和終點(diǎn)腺阳。end自增，直到遇到重復(fù)字符為止；從重復(fù)字符出現(xiàn)的位置之后1位重新開(kāi)始掃描胚委。
陷阱：重新開(kāi)始掃描的位置；循環(huán)結(jié)束條件
代碼：
class Solution:
# @param {string} s
# @return {integer}
def lengthOfLongestSubstring(self, s):
len_max = 0
start = 0
sub_string = ''
for end in xrange(len(s)):
if s[end] not in sub_string:
sub_string += s[end]
else:
len_max = max(len_max, len(sub_string))
while s[start] != s[end]:
start += 1
start += 1
sub_string = s[start : end + 1]
return max(len_max, len(sub_string))
以上解法可求出最大無(wú)重復(fù)字符的子串本身，由于題目只要求求出最大無(wú)重復(fù)字符的子串的長(zhǎng)度痴颊，因此可用Python集合（set）類(lèi)型略作優(yōu)化如下：
class Solution:
# @param {string} s
# @return {integer}
def lengthOfLongestSubstring(self, s):
length = 0
char_set = set()
start = end = 0
while start < len(s) and end < len(s):
if s[end] in char_set:
length = max(length, end - start)
char_set.remove(s[start])
start += 1
else:
char_set.add(s[end])
end += 1
return max(length, end - start)
另外，用Python字典（dict）進(jìn)行上述優(yōu)化也是可行的屡贺，該字典記錄了字符到下標(biāo)的反向索引蠢棱，代碼如下：
class Solution:
# @param {string} s
# @return {integer}
def lengthOfLongestSubstring(self, s):
start = len_max = 0
char_dict = {}
for i in range(len(s)):
if s[i] in char_dict and start <= char_dict[s[i]]:
start = char_dict[s[i]] + 1
else:
len_max = max(len_max, i - start + 1)
char_dict[s[i]] = i
return len_max
最后，使用enumerate和Python字典的get方法可使代碼更簡(jiǎn)潔：
class Solution:
# @param {string} s
# @return {integer}
def lengthOfLongestSubstring(self, s):
max_length, start, char_dict = 0, 0, {}
for idx, char in enumerate(s, 1):
if char_dict.get(char, -1) >= start:
start = char_dict[char]
char_dict[char] = idx
max_length = max(max_length, idx - start)
return max_length
