---
# System prepended metadata

title: "\n    Leetcode 3. Longest Substring Without Repeating Characters\n"
tags: [String]

---

###### 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>