題目連結(https://leetcode.com/problems/longest-substring-without-repeating-characters/description/)

Given a string s, find the length of the longest substring without duplicate characters.

今天來做 medium ，字串比對的題目，並探討不同的資料結構、sliding window演算法的應用

1. Repeat（題目重複確認）

• 輸入：字串 s
• 輸出：s 中不含重複字元的最長子字串
• 前提：
  • 0 <= s.length <= 5 * 10＾4 邊界條件
  • s consists of English letters, digits, symbols and spaces.
  • s的型態可能是英文字母、位元、符號、空格

2. Examples（舉例確認理解）

pkew 不行，因為不是子字串，雖然把字串中無重複字母都挑出來，但不滿足 substring 的定義。

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

3. Approach（解題思路）

方法 1：暴力法

• hash set＋雙層 for loop
• 思路：遍歷所有可能的子字符串，並檢查每個子字串是否有重複字符，找出最長的無重複字符的子字串。
• 時間複雜度：O(n^2)，因為需要遍歷每一個子字串，而每個子字串的比較操作時間為 O(n)。
• 空間複雜度：O(n)，需要額外的空間來存儲子字串。

方法 2：滑動視窗 (Sliding Window)

• 資料結構一樣用hash set，但另用兩個指標 i 和 j 分別表示滑動視窗的左右邊界。
• i 是開始位置，j 是結束位置，隨著 j 的增加，擴展視窗，並檢查是否有重複字符。
• 如果有重複字符，則移動 i 指標來縮小視窗，直到視窗中的字符不再重複。
• 時間複雜度：O(n) 每個字符最多會進入和退出滑動視窗一次
• 空間複雜度：O(n)

4. Code（C++）

方法一：暴力法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            unordered_set<char> set;
            for (int j = i; j < s.size(); j++) {
                if (set.find(s[j]) != set.end()) {//發現重複字串
                    break;
                }
                set.insert(s[j]); //不重複就加入 set 中
            }
            res = max(res, (int)set.size()); //更新最長的子字串長度
        }
        return res;
    }
};

方法二：滑動視窗

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> set;
        int i = 0, maxlength = 0;
        
        for (int j = 0; j < s.size(); j++) {
            // 移動左邊界，直到當前字符不重複
            while (set.find(s[j]) != set.end()) {//發現重複字符
                set.erase(s[i]);
                i++;
            }
            set.insert(s[j]);  // 加入當前字符到集合
            maxlength = max(maxlength, j - i + 1);  // 更新最大長度
        }
        
        return maxlength;
    }
};

方法三：滑動視窗（hash map優化版）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> mp;
        int l = 0, res = 0;

        for (int r = 0; r < s.size(); r++) {
            if (mp.find(s[r]) != mp.end()) {
                l = max(mp[s[r]] + 1, l);
            }
            mp[s[r]] = r;
            res = max(res, r - l + 1);
        }
        return res;
    }
};

5. Test 範例

假設 s = "pwwkew"

1. 初始化：set = {}, i = 0, maxLength = 0
2. j = 0: set.insert('p') → set = {'p'} → maxLength = 1
3. j = 1: set.insert('w') → set = {'p', 'w'} → maxLength = 2
4. j = 2: set.find('w') != set.end() → i = 1, set.erase('p') → set = {'w'}
5. j = 2: set.insert('w') → maxLength = 2
6. j = 3: set.insert('k') → set = {'w', 'k'} → maxLength = 3
7. j = 4: set.erase('w') → i = 2, set = {'k'}
8. j = 4: set.insert('k') → maxLength = 3
9. 最終返回 maxLength = 3

6. 相關題目與延伸概念

• 438. Find All Anagrams in a String：考察字串的滑動視窗技巧。
• 76. Minimum Window Substring：這是一道與滑動視窗有關的問題，並且需要處理字母的包含關係。
• 344. Reverse String：基本的字串反轉問題。

7. 補充：語法＆注意事項

• 滑動視窗的思路通過兩個指標 i 和 j 管理一個區間 [i, j]，這個區間內不包含重複字符。
• set.end()：這是一個特殊的迭代器，它指向集合的結尾，表示在集合中找不到該元素。
• set.find(s[j]) != set.end()：這裡我們是在檢查 s[j] 是否存在於 set 中。
  • 如果存在，find() 會返回一個有效的迭代器，這個迭代器不是 set.end()，所以條件為 true，進入 while 迴圈
  • 如果 s[j] 不在 set 中，find() 會返回 set.end()，條件為 false，跳過 while 迴圈。

ps. 部分內容經 AI 協助整理