主題: 學習筆記
LeetCode 3：TypeScript 最長不重複子字串，從回退重掃到 sliding window
保留一次回退重掃的嘗試，說明為何最壞為 O(n²)，再改為單次走訪的 Map sliding window。
這次先用兩個指標和 Map 解題。第一版遇到重複字元時會重設視窗，再從較早的位置重新掃描。它能得到正確答案，但右指標會倒退。第二版只讓右指標向前，才是這題需要的 O(n) 解法。
題目
對應原題：LeetCode 3：Longest Substring Without Repeating Characters
給定字串 s，回傳不含重複字元的最長連續子字串長度。子字串必須連續，因此 "pwke" 不是 "pwwkew" 的有效答案。
暴力解
從每個起點向右延伸，直到遇到重複字元。對每個起點都建立一個 Set，時間最壞是 O(n²)，額外空間最多 O(n)。
function lengthOfLongestSubstringBruteForce(s: string): number {
let longest = 0;
for (let start = 0; start < s.length; start += 1) {
const seen = new Set<string>();
for (let end = start; end < s.length; end += 1) {
if (seen.has(s[end])) break;
seen.add(s[end]);
longest = Math.max(longest, end - start + 1);
}
}
return longest;
}我第一版的回退重掃作法
第一版先處理空字串和單一字元，接著用 p1、p2 表示視窗兩端，並用 Map 記錄字元上次出現的索引。以下保留原本控制流程，只補上 Map 的型別。
function lengthOfLongestSubstring(s: string): number {
if (s.length === 0) return 0;
if (s.length === 1) return 1;
let res = 1;
const map = new Map<string, number>();
let p1 = 0;
let p2 = 1;
map.set(s[p1], p1);
while (p2 < s.length) {
if (map.has(s[p2])) {
p1 = map.get(s[p2])! + 1;
p2 = p1 + 1;
res = Math.max(map.size, res);
map.clear();
map.set(s[p1], p1);
} else {
map.set(s[p2], p2);
res = Math.max(map.size, res);
p2 += 1;
}
}
return res;
}這版不是 O(n log n)，因為沒有排序。問題在於遇到重複字元時，p2 被設回 p1 + 1，已掃過的字元會再被掃一次。
例如字串先有一段很長的不重複前綴，後面又重複同一段。每次偵測到重複字元，都可能從前一個位置重走大段字串。最壞情況是 O(n²)。Map 最多也會保存目前視窗內的不同字元，所以額外空間是 O(n)，不是 O(1)。
我改良的 Map sliding window
改良版保留每個字元最近一次出現的位置。右指標每回合只前進一格，不清空 Map，也不回退。若字元上次出現的位置仍在目前視窗裡，左指標直接跳到那個位置的下一格。
function lengthOfLongestSubstring(s: string): number {
const lastSeen = new Map<string, number>();
let left = 0;
let longest = 0;
for (let right = 0; right < s.length; right += 1) {
const char = s[right];
const previous = lastSeen.get(char);
if (previous !== undefined && previous >= left) {
left = previous + 1;
}
lastSeen.set(char, right);
longest = Math.max(longest, right - left + 1);
}
return longest;
}空字串不需要特別處理，因為迴圈不會執行，初始值 0 就是答案。單一字元也會自然得到長度 1。
Map 保存每個字元最近的位置。它會留下已經在視窗左側的舊索引，因此判斷時一定要保留 previous >= left。少了這個條件，像 "abba" 這種字串會把左指標往回移，視窗重新包含重複字元。
為何這版是正確的
每輪迴圈開始時，s[left..right - 1] 沒有重複字元，lastSeen 保存各字元最近一次出現的索引。
讀到 s[right] 後，若它最近一次出現的位置在目前視窗內，將 left 移到該位置右側，就能移除唯一的衝突。若最近位置已在視窗左側，維持 left 不動。更新 lastSeen 後，s[left..right] 仍沒有重複字元，因此可以用 right - left + 1 更新最長長度。
右指標總共走 n 次，左指標只會向右走，兩者都不會回退。面試中通常把 Map 查詢和寫入視為平均 O(1)，因此總時間是 O(n)。Map 最多保存不同字元的數量，額外空間是 O(min(n, c))，一般以 O(n) 表示，c 是可出現的不同字元數。
ASCII 固定陣列版本
若輸入已保證只含 7-bit ASCII，可以用固定 128 格陣列保存上次位置。它沒有改變漸近時間，仍是 O(n)，但避開了 Map 的雜湊與動態配置成本。因為陣列固定為 128 格，額外空間是 O(1)。
這不是通用 JavaScript 字串的替代品。charCodeAt() 讀的是 UTF-16 code unit，非 ASCII 文字應繼續使用 Map，或先確認需求要以 code unit 還是 Unicode code point 計算。
function lengthOfLongestSubstringAscii(s: string): number {
const lastSeen = new Int32Array(128).fill(-1);
let left = 0;
let longest = 0;
for (let right = 0; right < s.length; right += 1) {
const code = s.charCodeAt(right);
if (code >= lastSeen.length) {
throw new RangeError("This implementation only accepts ASCII input.");
}
left = Math.max(left, lastSeen[code] + 1);
lastSeen[code] = right;
longest = Math.max(longest, right - left + 1);
}
return longest;
}最小驗證
import assert from "node:assert/strict";
assert.equal(lengthOfLongestSubstring("abcabcbb"), 3);
assert.equal(lengthOfLongestSubstring("bbbbb"), 1);
assert.equal(lengthOfLongestSubstring("pwwkew"), 3);
assert.equal(lengthOfLongestSubstring("abba"), 2);
assert.equal(lengthOfLongestSubstring("tmmzuxt"), 5);
assert.equal(lengthOfLongestSubstring(""), 0);
assert.equal(lengthOfLongestSubstringAscii("a b!a"), 4);常見陷阱
- 只要
Map有該字元就移動左指標。上次出現的位置可能已經在視窗外，必須比較previous >= left。 - 遇到重複字元就清空
Map。這會遺失可重用的索引，也讓右指標回頭掃描。 - 把
Map的空間說成O(1)。除非字元集大小固定，例如 ASCII 的 128 格陣列，否則它可能保存n筆資料。 - 把 subsequence 當成 substring。這題只接受連續片段。
- 把 ASCII 陣列直接套到任意 Unicode 文字。先確認字元範圍和計數單位。
可遷移的思路
這題的視窗條件是「不含重複字元」。當右側加入新字元導致條件失效時，不必重建整個視窗，只要把左側移到足以消除衝突的位置。這是可變長 sliding window 的基本模式。