LeetCode 3. 無重複字元的最長子串（滑動視窗圖解）

3. 無重複字元的最長子串

題目描述

給定一個字串 s，請你找出其中不含有重複字元的最長子串的長度。

範例 1

輸入：s = "abcabcbb"
輸出：3
解釋：因為無重複字元的最長子串是 "abc"，所以其長度為 3。注意 "bca" 和 "cab" 也是正確答案。

範例 2

輸入：s = "bbbbb"
輸出：1
解釋：因為無重複字元的最長子串是 "b"，所以其長度為 1。

範例 3

輸入：s = "pwwkew"
輸出：3
解釋：因為無重複字元的最長子串是 "wke"，所以其長度為 3。
請注意，答案必須是子串的長度，"pwke" 是一個子序列，不是子串。

限制

• 0 <= s.length <= 10^5
• s 由英文字母、數字、符號和空格組成

本文題解程式碼整理自 LeetCode 題解作者「灵茶山艾府」，題解連結。思路說明與圖解為自行補充。

前置知識：不定長滑動視窗

前幾篇（2841、2461、1423）的視窗長度都固定為 k。這題的視窗長度不固定：right 往右走一格就把新字元加入視窗，如果視窗內出現重複，就不斷把 left 往右移（縮小視窗），直到沒有重複為止。

每個字元最多被 right 加入一次、被 left 移出一次，所以整體是 O(n)。

兩種寫法的差別只在於「怎麼記錄視窗裡有哪些字元」：

• 寫法一：用計數表 cnt，記錄每個字元在視窗內出現幾次。先加入再檢查，cnt[c] > 1 就縮小。
• 寫法二：用集合 has，只記錄視窗內有沒有這個字元。先檢查再加入，has[c] 為真就先縮小，沒有重複才加入。

方法一：哈希表（整型陣列計數）

思路

1. right 向右枚舉，把 c = s[right] 的計數加一。
2. 若 cnt[c] > 1，代表視窗內有重複，用 while 不斷移出左端字元（cnt[s[left]]--、left++），直到 cnt[c] == 1。
3. 此時視窗內沒有重複，用 right - left + 1 更新答案的最大值。

圖解（可互動）

用範例 1：s = "abcabcbb"。注意第 3 個字元 a 再次出現時，cnt["a"] 變成 2，視窗會縮小到把舊的 a 移出為止。

上一步 下一步 重置

s = "abcabcbb"（先加入，有重複再縮小）

窗口 [left, right] 造成重複的字元 入 = 剛加入 出 = 剛移出

窗口長度0

最長長度 ans0

解法（灵茶山艾府）

class Solution {
    public int lengthOfLongestSubstring(String S) {
        char[] s = S.toCharArray(); // 轉換成 char[] 加快效率（忽略帶來的空間消耗）
        int n = s.length;
        int ans = 0;
        int left = 0;
        int[] cnt = new int[128]; // 也可以用 HashMap<Character, Integer>，這裡為了效率用的陣列

        for (int right = 0; right < n; right++) {
            char c = s[right];
            cnt[c]++;
            while (cnt[c] > 1) { // 視窗內有重複字母
                cnt[s[left]]--; // 移除視窗左端點字母
                left++; // 縮小視窗
            }
            ans = Math.max(ans, right - left + 1); // 更新視窗長度最大值
        }
        return ans;
    }
}

複雜度分析

• 時間複雜度：O(n)，其中 n 為 s 的長度。注意 left 至多增加 n 次，所以整個二重迴圈至多循環 O(n) 次。
• 空間複雜度：O(|Σ|)，其中 |Σ| 為字元集合的大小，本題中字元均為 ASCII 字元，所以 |Σ| ≤ 128。

方法二：哈希集合（布林陣列）

思路

視窗內不可能有重複字元，所以其實不需要知道「出現幾次」，只要知道「有沒有」就夠了：

1. right 向右枚舉，c = s[right]。
2. 加入 c 之前先檢查：若視窗內已經有 c（has[c] 為真），再加入就會重複，所以先用 while 不斷移出左端字元（has[s[left]] = false、left++），直到視窗內沒有 c。
3. 加入 c（has[c] = true），用 right - left + 1 更新答案的最大值。

圖解（可互動）

同樣用範例 1。和方法一比較：這裡在遇到重複時，是先縮小、再加入，所以窗口不會短暫出現重複字元。

上一步 下一步 重置

s = "abcabcbb"（先縮小到沒重複，再加入）

窗口 [left, right] 造成重複的字元 入 = 剛加入 出 = 剛移出

窗口長度0

最長長度 ans0

解法（灵茶山艾府）

class Solution {
    public int lengthOfLongestSubstring(String S) {
        char[] s = S.toCharArray(); // 轉換成 char[] 加快效率（忽略帶來的空間消耗）
        int n = s.length;
        int ans = 0;
        int left = 0;
        boolean[] has = new boolean[128]; // 也可以用 HashSet<Character>，這裡為了效率用的陣列

        for (int right = 0; right < n; right++) {
            char c = s[right];
            // 如果視窗內已經包含 c，那麼再加入一個 c 會導致視窗內有重複元素
            // 所以要在加入 c 之前，先移出視窗內的 c
            while (has[c]) { // 視窗內有 c
                has[s[left]] = false;
                left++; // 縮小視窗
            }
            has[c] = true; // 加入 c
            ans = Math.max(ans, right - left + 1); // 更新視窗長度最大值
        }
        return ans;
    }
}

複雜度分析

• 時間複雜度：O(n)，其中 n 為 s 的長度。left 至多增加 n 次，所以整個二重迴圈至多循環 O(n) 次。
• 空間複雜度：O(|Σ|)，本題中字元均為 ASCII 字元，所以 |Σ| ≤ 128。