題目
給定一個字符串饭玲，請你找出其中不含有重復字符的最長子串的長度。
示例
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"叁执，所以其長度為 3茄厘。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1谈宛。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"次哈，所以其長度為 3。
請注意吆录，你的答案必須是 子串 的長度窑滞，"pwke" 是一個子序列，不是子串恢筝。
解答
方案1
我們首先考慮用暴力求解法哀卫，探究字符串的每一個子串是否不含重復字符，并記錄不含重復字符的最長子串撬槽。
這里此改，我們設置i，j為子串兩端字符在原字符中的下標索引侄柔，用lambda表達式定義一個簡易函數no_repetitive_chars共啃，用于判斷輸入的字符串是否沒有重復字符，如果沒有返回True暂题。用cur_len記錄當前非重復字符串的長度勋磕，用max_len記錄當前為止最大非重復子串長度。所有子串的可能有(N+1)*N/2個敢靡，需要一一判斷挂滓。
class Solution:
def lengthOfLongestSubstring(self, s):
no_repetitive_chars = lambda s: len(list(cur_chars)) == len(set(list(cur_chars)))
max_len = 0
for i in range(len(s)):
for j in range(i+1, len(s)+1):
cur_chars = s[i:j] # 取當前子串
if no_repetitive_chars(cur_chars):
cur_len = len(cur_chars) # 當前子串長度
max_len = max(cur_len, max_len) # 當前最長子串長度
return max_len
不出意料，代碼超時啸胧，我們需要更換思路赶站。
方案2
如何做到只遍歷一次？為了獲得更好的時間性能纺念，我們采用算法優(yōu)化中常用的以空間換時間策略贝椿，設輸入字符串為s，從頭到尾遍歷字符串：
1.創(chuàng)建臨時字符串變量cur_str陷谱，這個字符串中烙博，沒有重復字符瑟蜈，并且最后一個字符是當前遍歷到的字符；
2.定義下標字典（哈希表）index_dict渣窜，字典的鍵是cur_str中的每一個字符铺根，值為字符對應的s中的下標；
3.從頭到尾遍歷字符串乔宿，查看當前字符串cur_char是否在cur_str中位迂，如果出現(xiàn)過，從字典中取出該字符的位置prev_index详瑞，為了保證cur_str中元素不重復掂林，需要把cur_str中第一個字符的開始位置start_index（相對于s）移動到prev_index+1，相當于從prev_index+0.5位置截斷cur_str并取后半部分坝橡；
4.同時更新下標字典index_dict泻帮，刪除在start_index之前的所有字符記錄，確保index_dict中的所有元素只包含cur_str中的所有字符计寇。
需要留意的是锣杂，start_index，prev_index饲常，cur_index等下標變量都是相對于輸入字符s的位置蹲堂。
class Solution(object):
def lengthOfLongestSubstring(self, s):
def remove_previous_chars(index_dict, index):
previous_chars = []
for char in index_dict.keys():
if index_dict[char] < index:
previous_chars.append(char)
for char in previous_chars:
index_dict.pop(char)
# 相當于{key: value for key, value in index_dict.items() if value >= index}
# 但是執(zhí)行會出錯不知為何
if s is None or len(s) == 0: # 特殊情況，特殊對待
return 0
max_len = start_index = 0
index_dict = {} # 下標字典贝淤，key為字符柒竞，value為下標
for cur_index in range(len(s)):
cur_char = s[cur_index] # 當前字符
if cur_char in index_dict:
start_index = index_dict[cur_char] + 1 # 更新當前字符串的起始位置
remove_previous_chars(index_dict, start_index) # 更新下標字典
# cur_str = s[cur_index: start_index+1] # 當前字符串
# cur_len = len(cur_str) # 當前字符串長度
cur_len = cur_index - start_index + 1 # 當前字符的長度
index_dict[cur_char] = cur_index # 加入當前字符及其下標
max_len = max(max_len, cur_len) # 當前最大長度
return max_len
代碼通過時間限制，耗時280ms播聪。
方案3
如何能夠不用反復刪除字典中的元素朽基？這里我們的字典index_dict性質改變，不只用來記錄cur_str中的所有字符离陶，而是遍歷到當前位置cur_index后之前所有s中出現(xiàn)過的字符及其距離cur_index最近的下標稼虎。這樣就要求我們不能隨意更新cur_str的開始位置start_index，這時招刨，我們更新start_index不僅需要當前字符在index_dict中出現(xiàn)過霎俩，位置為prev_index，而且需要保證出現(xiàn)的位置在cur_str中沉眶，這就要求上次出現(xiàn)位置prev_index<當前字符串的開始位置cur_index打却，省去了刪除字典元素的步驟。
class Solution(object):
def lengthOfLongestSubstring(self, s):
if s is None or len(s) == 0:
return 0
max_len = start_index = 0
index_dict = {}
for cur_index in range(len(s)):
cur_str = s[cur_index]
if cur_str in index_dict and index_dict[cur_str] >= start_index:
start_index = index_dict[cur_str] + 1
cur_len = cur_index - start_index + 1
index_dict[cur_str] = cur_index
max_len = max(max_len, cur_len)
return max_len
代碼通過時間88ms谎倔，這也是網上廣泛采用的方法柳击。
如有任何疑問，歡迎評論區(qū)留言片习。
