題目資訊

• 題目編號: 3
• 題目連結: Longest Substring Without Repeating Characters
• 主題: Hash Table, String, Sliding Window

題目敘述

給定一個字串 $s$，找出沒有重複字符的最長 子字串的長度。

範例 1:

輸入: s = "abcabcbb"
輸出: 3
解釋: 答案是 "abc"，長度為 3。

範例 2:

輸入: s = "bbbbb"
輸出: 1
解釋: 答案是 "b"，長度為 1。

範例 3:

輸入: s = "pwwkew"
輸出: 3
解釋: 答案是 "wke"，長度為 3。
注意答案必須是一個子字串，"pwke" 是子序列而不是子字串。

約束條件:

• $0 \leq s.length \leq 5 \times 10^4$
• $s$ 由英文字母、數字、符號和空格組成。

直覺

尋找最長沒有重複字符的子字串的問題可以有效地通過滑動窗口的概念來解決。滑動窗口方法提供了一種檢查整體數據子集（在本例中為字串的一部分）的方法，同時動態調整其大小。通過使用兩個指針（窗口的起始指針和結束指針），我們可以高效地遍歷字串。這裡的關鍵洞察是保持字符出現的記錄，並調整窗口邊界以確保窗口內沒有字符重複。

解法

為了解決這個問題，我們使用滑動窗口方法，利用兩個指針：left 和 right。另外，使用一個哈希映射（在 C++ 中為 map）來記錄每個字符的最後出現索引。主要目的是調整右指針來擴大窗口，並使用左指針確保窗口保持有效（即沒有重複字符）。

1. 初始化：我們首先初始化一個 characterCount map 來儲存當前窗口中每個字符的個數。我們還設置兩個整數變數 left 和 right 為 0，代表窗口的開始和結束。另一個整數 maxLength 初始化為 0，用以儲存迄今為止找到的最大有效子字串的長度。

2. 使用右指針迭代：我們通過 right 指針迭代遍歷字串。對於字串中的每個字符，執行以下步驟：

   • 增加當前 right 指針位置字符在 characterCount 中的計數。
   • 如果某個字符計數變為 2（表示在窗口內找到重複），進入 while 循環以調整窗口：
     • 減少當前 left 指針位置字符的計數。
     • 將 left 指針向右移動一步，從左側縮小窗口直到不再有重複字符。

3. 更新最大長度：確保當前窗口 [left, right] 有效（即無重複）後，計算其長度（right - left + 1），如果當前窗口長度超過之前的最大長度，則更新 maxLength。

4. 返回結果：在完成字串的 right 指針遍歷後，返回 maxLength，它存儲著找到的最長有效子字串的長度。

這種方法確保每個字符最多被處理兩次（一次由 right，一次由 left），從而使時間複雜度為 $O(n)$。鑒於問題的約束條件，這樣的效率是合適的。

程式碼

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 用於儲存每個字符最後出現索引的映射
        map<char, int> characterCount;
        
        int maxLength = 0; // 儲存找到的最大子字串長度
        int left = 0; // 用於滑動視窗的左指針
        int right = 0; // 用於滑動視窗的右指針

        // 使用右指針遍歷字串
        for (; right < s.size(); right++) {
            characterCount[s[right]]++; // 當前字符的計數加一
            
            // 如果找到重複的字符（計數變為2）
            while (characterCount[s[right]] == 2) {
                characterCount[s[left]]--; // 移除左指針指向的字符
                left++; // 移動左指針以縮小視窗
            }
            
            // 更新找到的最大子字串長度
            maxLength = max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
};

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 映射來存儲每個字符最後出現的索引
        characterCount = {}

        maxLength = 0  # 存儲找到的子字串的最大長度
        left = 0  # 滑動窗口的左指針
        right = 0  # 滑動窗口的右指針

        # 使用右指針遍歷字串
        for right in range(len(s)):
            characterCount[s[right]] = characterCount.get(s[right], 0) + 1  # 增加當前字符的計數
            
            # 如果發現重複的字符（計數變為2）
            while characterCount[s[right]] == 2:
                characterCount[s[left]] -= 1  # 移除左指針的字符
                left += 1  # 移動左指針以縮小窗口
            
            # 更新找到的最大子字串長度
            maxLength = max(maxLength, right - left + 1)
        
        return maxLength

複雜度分析

• 時間複雜度: $O(n)$. 此演算法使用滑動視窗方法，並利用兩個指針 left 和 right 來遍歷長度為 $n$ 的字串 s。每個字元最多會被處理兩次：第一次是當 right 指針遇到該字元時，第二次是如果該字元被算作重複而由 left 指針再次處理。這導致線性時間複雜度為 $O(n)$。

• 空間複雜度: $O(m)$，其中 $m$ 是輸入字串 s 中不同字元的數量。characterCount 映射可能會存儲來自字串的每個不同字元及其出現次數。在最壞情況下，如果所有字元都是不同的，則空間複雜度為 $O(m)$，並受到字符集大小的限制。若考慮英文字母、數字、符號和空格，$m$ 最多為 128。