###### tags: `String`
<h1>
Leetcode 3. Longest Substring Without Repeating Characters
</h1>
<ol>
<li>問題描述</li>
Given a string s, find the length of the longest substring without repeating characters.<br>

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring.
"pwke" is a subsequence and not a substring.

<li>Input的限制</li>
<ul>
<li>0 <= s.length <= 5 * 10^4</li>
<li>s consists of English letters, digits, symbols and spaces.</li>
</ul>
<br>

<li>思考流程</li>
<ul>
<li>暴力法(Brute force)</li>
直覺上，只要列出所有子字串( substring )，然後逐一確認每個子字串內有沒有重複的元素即可。同時，去記錄沒有重複元素的最長子串的長度，一旦發現有新的子字串比較長，就立刻做更新的動作，最後把最長的值回傳出去。
<br>
<br>
如果 input 字串的長度是 n，則總共有 n(n+1)/2 個子字串，確認每個子字串是否有重複的字母，worst case 需要遍歷 n 個字母，故整體的 time complexity 為 O(n^3)。在 space complexity 的部分，主要使用到一個串列來儲存 ASCII code 的代表值，確認是否子字串已經出現重複的字元(串列值大於 1 )，故如果 ASCII code 有 m 個字元，則 space complexity 是 O(m)。
<br>
<br>
Time Complexity: O(n^3); Space Complexity: O(m)
<br>
<br>
<li>Sliding Windows</li>
使用一張 table( list ) 利用其索引對應到可能字元的 ASCII or Unicode 值，該 list 元素的值，即是目前子字串該字元出現的次數。在 input 字串的某端給兩個指標 i 和 j，分別代表子字串的頭尾。j 指標掃過字元，會在表內更新該字元的出現紀錄，當表內某個字元的出現紀錄大於 1，則代表子字串出現重複的字元，必須移動 i 指標，使字串重新成為一個字元不重複的子字串。在 worst case 的情況下，指標 j 和 i 必須各自跑過一遍 input 字串，所以 time complexity 為 O(2n) = O(n)<br><br>
一種進階的優化方案是，利用 hash table 紀錄出現的字元值為 key，其下一個字元的索引為 value，一旦指標 j 記錄到了重複的字元出現在子字串內，指標 i 就可以直接跳到重覆字元的下一個字元，不用再逐個字元進行掃描。這樣做法的 time complexity 為 O(n)。Space complexity 方面，假設 ACSII code 有 m 個字元，input 字串有 n 個字元，當 n > m 時，則最差的情況就是所有 ASCII code 的字元都出現過一次，這時 space complexity 為 O(m)；若 n < m，則最多每個字串內的字元都被記錄一次，此時 space complexity 為 O(n)。
<br>
<br>
Time Complexity: O(n); Space Complexity: O(min(m, n))
<br>
<br>
</ul>
<li>測試</li>
<ul>
<li>test 1</li>
Input: digits = "abcac" ; Output: 3
</ol>