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.
王小二一大早拿了一個題目去找老馬幫忙。因為他的大學同學在同學群裡發了一道 Google 面試題，他想找老馬聊聊思路。
老馬看了看王小二手中的題目，大概的意思是輸入一個純小寫英文字母組成的字符串，輸出該字符串的最長的沒有重複字母的子串的長度。老馬一直很滿意王小二的勤奮好學，所以還是非常樂意跟王小二分享算法方面的思路。
老馬先問王小二自己的想法：「小二， 這道題你自己有什麼思路嗎？」
王小二回答道：「思路倒是有，我想到的方案是暴力法。」
「怎麼一個暴力法？具體說說吧！」
「就是用暴力方法，遍歷字符串所有的位置，以這個位置往前走，直到出現重複字母就停下來。然後返回所有結果中符合要求的字符串的長度的最大值。」 王小二擔心老王沒有挺清楚，接著解釋道：「具體地，可以用兩個指針維護子串的區間，每往前走一格，需要判斷當前位置的字符在區間是否重複。」
老馬點點頭：「你的這個暴力方法的時間複雜度是多少？」
王小二不好意思的說：「O(N^3)」
「嗯，複雜度有點高啊」 老馬笑著說：「你有想到優化的辦法嗎？」
王小二用手託著下巴想了一會後，不好意思的說：「沒有啥好辦法。」
「其實我們可以用 Hash 或者 Set 來降低查詢的時間複雜度」 老馬說：「這是一種非常常見的空間換時間的手法。你應該知道，在數組中搜索一個元素的複雜度是 O(N)， 但是在Hash或者Set 中搜索一個元素的複雜是 O(1)。」
老馬指了指王小二帶來的題目接著道：「結合你剛才的解法，其實我們可以把每次搜索過的字符加入 Hash/Set ， 這樣判斷元素是否重複部分的時間複雜度可以降到 O(1), 這樣整體的時間複雜度可以降低到 O(N^2)。」
王小二真是佩服老馬，三言兩語就能把時間複雜度降低一個數量級。
老馬接著說 ：「但是時間複雜度還是太高了。」
王小二點頭說：「是的。如果能將複雜度降低到O(N) 就好了。」
老馬說：「將這種類型的題目的複雜度降低到 O(N) 的方法還是很多的。我今天跟你講講兩個思路吧。」
「第一個思路叫做 two pointers， 中文名叫雙指針。雙指針在鍊表問題中應用特別廣泛，特別是在鍊表環路判斷和排序等方面。」
「本題的雙指針的用法是這樣的：分別用i, j 表示符合條件的字符串的左邊和右邊。如果 s[j+1] 不在當前的子串中, 那麼將s[j+1] 加入子串中，移動 j ; 如果 s[j+1] 存在於當前的子串中，那麼移動 i 到 當前子串 s[j+1] 字符出現的位置。 」
「懂了」 王小二讚嘆到 「這種解法真是精妙啊，只需要掃描一次字符串，時間複雜度降低到了 O(N) 。」
「嗯，還有一個方法，叫做滑動窗口」 老馬見王小二理解了雙指針的思路，就接著講起了滑動窗口。
「滑動窗口的思路在本題上跟雙指針法方法有點像，就是維護一個 [i, j ] 的區間，其他的操作跟 雙指針一樣。」
「當然」老馬頓了頓說 ：「其實也可以不一樣。我們可以用一個 Queue 來表示滑動窗口，當 s[j+1] 在 Queue 中的時候，我們就彈出這些元素：隊列的頭部到隊列中的s[i]的位置的元素。」
「這樣做有哪些不好的地方？」老馬突然拋出一個問題。
「我覺得用隊列來表示滑動窗口有兩個缺點：1，空間浪費，需要維護一個最大 N 大小的空間；2，時間複雜度也比雙指針要差，因為隊列每次只能移動一步，但是雙指針可以跳躍移動，更靈活。」
「對」，老馬欣慰的點點頭，王小二學習能力還是很強的。
「還有其他解法嗎？」 老馬接著問道。
「已經有三種解法啦，還有其他的解法？」 他表示很吃驚。
「一定有」， 老馬肯定的答道：「這道題還有一種非常精妙的解法，應該跟你分享一下。」
「啥方法」 王小二有點迫不及待了。
老馬沒有直接回答，而是說：「我們不是剛剛說了暴力嘛，我們的方案是不是從左往右掃描的？」
「是的」王小二肯定的答道。
「那你覺得從右往左掃描怎麼樣？」老馬笑著說。
王小二想了想，拍了拍自己的腦袋「對啊，如果從右往左掃，會降低複雜度。」
「這樣不會降低複雜度，是一種逆向思維」老馬示意他繼續講下去。
王小二接著說「假設當前的位置是 i , 那麼以 s[i] 結尾的符合要求的子串的最大長度有兩種可能。」
「如果s[i] 與前面的子串中的字符沒有重複，那麼最大長度就是 i + 1」
「如果s[i] 與前面的子串中的字符有重複， 那麼最大長度就是 i - 離i最近的出現字符s[i]的位置 + 1"
「對」 老馬高興的說 ：「你分析的很對。你的這個暴力方案還可以在優化嗎？」
「可以」， 王小二說：「你剛才分享了用Hash 的方式可以降低在一個 容器中尋找元素是否存在的時間複雜度。我覺得這個方案也可以用這個辦法。」
「贊啊！的確可以這麼做」 老馬說：「其實這種方法叫做記憶優化，就是我們緩存部分結果來減小時間複雜度。」
「小二，要不你把我們今天的談話總結一下吧？」老馬提了一個小要求。
「好的」，王小二愉快的答應了，畢竟他覺得今天的收穫還是很大的：「我明天早上給你。」
「對了這個題目還可以用 二分法和分治算法，有空你可以練練代碼。」 老馬給王小二布置了一個家庭作業。
晚上睡前前，王小二開始做總結，他想了想跟老馬的討論，寫下了如下幾個重點：
靈活運用數據結構，比如用 Hash/Set 等容器能將搜索元素的複雜度降低到 O(1)
雙指針 和 滑動窗口 在解決連續串的問題非常有效（連續的字符串或者鍊表），雙指針更靈活
對比思考：從右往左 比 從左往右 往往可以得到一些新的思路；將 i 作為條件終點，比將 i 作為條件起點能讓問題更簡單
掃描的過程中，做記憶優化可以顯著的降低時間複雜度