3. Longest Substring Without Repeating Characters

──────────────────────────────────────────────────────────────────────

給一個字串，找出不含重複字元的最長子字串長度。注意是「子字串」（連續）而不是「子序列」。

思路

這一題其實是可以透過暴力解法想辦法算出來的，那就是窮舉出所有的子字串，並且檢查每一個子字串有沒有重複的字元。時間複雜度約為 $O (n^{3})$ 。

不過這一題的做法算是雙指針的初始練習題，要第一次寫就想到的確不容易，不過可以從這個題目練習核心的觀念。

原先的暴力窮舉法最主要是不斷的重複掃描重複的地方 —— 檢查 s[0..5] 的時候明明已經知道 s[0..4] 沒有重複了，下一輪卻又從頭數一遍。如果使用雙指針的話，就可以盡可能地減少重複掃描的動作：右指針只前進、左指針只前進，兩個都不回頭。

要用什麼記錄窗口內容

要做到這個目的，我們還需要一個方法來記錄不重複的字元。我一開始是想到用 set() 來記錄，不過這樣的話我們沒辦法知道次數，而且這個重複字元不一定是在最後一個字元。

這個轉折是關鍵：set 只能回答「在不在」，但收縮窗口時我要知道「還剩幾個」才知道什麼時候可以停。所以我想到了用 Hash Table 來記錄 —— 每次掃描一個字元的時候，我們就馬上檢查這個字元是不是出現兩次了，那這時候慢指針就會開始往右掃描，每次掃到一個字元，就從 Hash Table 上減去一個計數，直到計數只剩一次為止。

滑動窗口的四個問題

這題套用的就是 Sliding Window 模板那套框架，動手前先把四個問題答完：

問題	這題的答案
窗口增大時要更新哪些資訊？	計算每個字元的計數
何時要收縮窗口？	當該字元的計數大於 1
收縮時要更新哪些資訊？	減少該字元的計數，直到小於或等於 1
答案在「擴大」還是「收縮」時更新？	收縮完窗口之後

最後一個問題最容易錯。這題求的是最長，所以要等窗口重新變成合法的（沒有重複）才能取 max —— 收縮的過程中窗口是不合法的，那時候的長度不能算。反過來如果題目求最短（例如 76. Minimum Window Substring），就要在收縮的每一步都更新答案，因為越縮越短。

解題方向

暴力解

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        def check(start, end):
            chars = defaultdict(int)
            for i in range(start, end + 1):
                c = s[i]
                chars[c] += 1
                if chars[c] > 1:
                    return False
            return True

        n = len(s)

        res = 0
        for start in range(n):
            for end in range(start, n):
                if check(start, end):
                    res = max(res, end - start + 1)
        return res

滑動窗口

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 0
        res = 0
        visited = defaultdict(int)

        while right < len(s):
            char = s[right]
            right += 1
            visited[char] += 1

            while visited[char] > 1:
                d = s[left]
                left += 1
                visited[d] -= 1
            res = max(res, right - left)

        return res

有一個地方很容易搞混：right += 1 是在讀完字元之後馬上做的，所以進到 res = max(...) 那一行時，right 已經指向「窗口外的下一格」。於是窗口是左閉右開的 [left, right)，長度就是 right - left，不是 right - left + 1。

如果改成 for right in range(len(s)) 的寫法（模板裡是這樣），right 就還在窗口內，長度才要 +1。兩種都對，但混用就會差一。

內層 while 只需要檢查 visited[char]（剛進來的那個字元），不用檢查整個窗口 —— 因為窗口在這個字元進來之前是合法的，唯一可能的重複就是它。

補充

同一個「求最長」的骨架：424. Longest Repeating Character Replacement（窗口條件換成「可替換次數不超過 k」）、1004. Max Consecutive Ones III（窗口裡的 0 不超過 k 個）。

求最短的對照：76. Minimum Window Substring、209. Minimum Size Subarray Sum。骨架一樣，差別只在答案更新的時機，見 Sliding Window 模板。

複雜度

暴力解

時間 $O (n^{3})$ — $O (n^{2})$ 個子字串，每個再花 $O (n)$ 檢查有沒有重複
空間 $O (\min (n, | Σ |))$ — check 裡的計數表

滑動窗口

時間 $O (n)$ — left 和 right 都只單向前進，各走一趟；內層 while 的總執行次數也是 $O (n)$ ，不是每次都 $O (n)$
空間 $O (\min (n, | Σ |))$ — 窗口裡最多裝下字元集大小那麼多種字元

其中 $n$ 是字串長度、 $| Σ |$ 是字元集大小（只有小寫英文就是 26）。內層迴圈不會讓時間變成 $O (n^{2})$ —— 因為 left 從頭到尾只走過一遍，所有收縮加起來也只有 $n$ 步。