原題：
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
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.
分析：
首要要判斷non-repeating characters鄙币，考慮要用字典或集合熏矿。
遍歷全部子字符串需要O(N2)锦茁，每個(gè)字符串判斷non-repeating chars需要O(n)，所以最壞需要時(shí)間O(n3)和空間O(n)暴凑。但由于構(gòu)建子字符串和使用字典判斷字符獨(dú)特性可以同時(shí)進(jìn)行，所以brute force應(yīng)該只需要O(n2)艰匙。
考慮先實(shí)現(xiàn)brute force然后進(jìn)行優(yōu)化蹭越。
解題：
第一版：Brute Force
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
res = 0
for i in range(len(s)):
letters = set()
j = i
while j < len(s) and s[j] not in letters:
letters.add(s[j])
j += 1
res = max(res, len(letters))
return res
Time Limit Exceeded
時(shí)間是O(n2)拖陆，但仍不出所料的超時(shí)了弛槐。
第二版：從brute force剪枝，已經(jīng)構(gòu)建出的子字符串字典不用重復(fù)構(gòu)建依啰。使用ordered dict來(lái)實(shí)現(xiàn)一個(gè)滑動(dòng)窗口乎串，右側(cè)enqueue，左側(cè)dequeue速警。當(dāng)需要enqueue的字符已經(jīng)存在時(shí)叹誉，dequeue已存在的字符和它左邊的所有字符。
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
res = 0
letters = collections.OrderedDict()
for letter in s:
inserted = False
while not inserted:
if letter not in letters:
letters[letter] = 1
inserted = True
res = max(res, len(letters))
else:
letters.popitem(last = False)
return res
Runtime: 389 ms
Accepted闷旧，但是速度仍然不夠理想长豁。
使用ordered dict，在pop左側(cè)字符的時(shí)候是O(n)的時(shí)間忙灼。雖然比brute force有優(yōu)化匠襟，但總時(shí)間依然是O(n2)。
第三版：在計(jì)算子字符串長(zhǎng)度的時(shí)候该园，我們并不需要考慮每一個(gè)字符酸舍，只需要知道它的開始和結(jié)束的index就可以了。因此爬范，我們實(shí)際需要的是一個(gè)字典父腕，里面保存每一個(gè)已經(jīng)遍歷過的字符的index（重復(fù)字符取最大值）。并且在每次遇到重復(fù)字符的時(shí)候青瀑，用字典里保存的index來(lái)計(jì)算新的開始index璧亮。這樣每次遍歷結(jié)束時(shí)，我們可以保證開始和當(dāng)前index之間的子字符串是沒有重復(fù)字符的斥难。
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
res = start = 0
discovered = {}
for idx, val in enumerate(s):
if val in discovered:
start = max(start, discovered[val] + 1)
discovered[val] = idx
res = max(res, idx - start + 1)
return res
Runtime: 82 ms
時(shí)間：O(n)
空間：O(n)
