[LeetCode] 3. Longest Substring Without Repeating Characters

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.

參考 水中的魚 的blog 的圖

http://fisherlei.blogspot.com/2012/12/leetcode-longest-substring-without.html

找出最長的不重複 子串

用 Two pointer 加上 hash table 來解

掃一次 字串 如果當前的 字元 出現過了 把left pointer 移到 之前出現此字元 的右邊 開始新的一輪

以上圖為例 round 1, x 在index 5 重複了. round 2 就從x 第一次出現的地方 index 2 的右邊+1 也就是

index 3 開始搜索