3. Longest Substring Without Repeating Characters

📘 題目敘述

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

條件限制

• 0 ≤ s.length ≤ 5 × 10^4
• s 由英文字母、數字、符號與空白字元組成

🧠 解題思路

我把這題想成一個「從左到右掃描字串，同時維持一段目前不重複的連續區間」的過程。

在掃描的同時，我會隨時記錄目前這段區間的長度，並更新目前看過的最大值。

所有變數

• sub：目前維持的「不包含重複字元」的子字串，可以視為一個直覺版的滑動視窗
• ans：目前為止找到的最長不重複子字串長度
• check：用來標記「這一輪是否已經處理過重複字元」

一開始的處理方式是：

• 若字串為空，直接回傳 0
• 否則先將 sub 設為第一個字元，代表目前視窗長度為 1
• 接著從第二個字元開始，逐一往右掃描

接下來我依序處理每一個 s[i]，會出現以下幾種情況：

情況一：s[i] 沒有出現在 sub 中（沒有重複）

• 表示目前的子字串仍然符合「不重複」的條件
• 可以直接將 s[i] 加到 sub 後面
• 視窗向右擴張一格

情況二：s[i] 出現在 sub 中（發生重複）

• 代表若直接加入 s[i]，子字串中會出現重複字元
• 因此需要將子字串的左邊界往右移動

當在 sub[j] 找到與 s[i] 相同的字元時：

• 將 sub 改成 sub.substr(j + 1)
  • 也就是捨棄重複字元以及它之前的所有字元
• 再將目前的 s[i] 加入新的 sub
• 並將 check 設為 true，表示這一輪已經處理過重複情況

這樣可以確保新的 sub 仍然是不包含重複字元的連續子字串。

為什麼要在內層迴圈中更新 ans？

在掃描 sub 的過程中：

• sub 代表的是當下合法的子字串
• 無論接下來是否遇到重複，這一刻的長度都可能成為目前的最大值

因此我會在內層迴圈中，用目前的 sub.size() 持續更新 ans。

另外，在整個掃描結束後：

• 再額外比較一次最後的 sub.size()，避免漏掉最後一段子字串

最後回傳

• 回傳 ans
• 代表整個字串中，不包含重複字元的最長子字串長度

💻 程式碼實作

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) {
            return 0;
        }
        string sub = s.substr(0, 1);
        int ans = 0;
        for (int i = 1; i < s.size(); i++) {
            bool check = false;
            for (int j = 0; j < sub.size(); j++) {
                if (ans < sub.size()) {
                    ans = sub.size();
                }
                if (s[i] == sub[j]) {
                    sub = sub.substr(j + 1);
                    sub.push_back(s[i]);
                    check = true;
                    break;
                }
            }
            if (!check) {
                sub.push_back(s[i]);
            }
        }
        ans = max(ans, (int)sub.size());
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/longest-substring-without-repeating-characters/