主題: 學習筆記

LeetCode 424：TypeScript 最長重複字元替換，理解 sliding window 與歷史最高頻率

保留這次的 frequency-counting sliding window 解法，說明 maxFreq 為何可以不隨左指標倒退。

這題讓我卡住的地方，是視窗左側已移動後，maxFreq 卻沒有跟著減少。直覺上很像資料過期了。實作後才理解，這個歷史最高頻率正是讓兩個指標都只往右走的原因。

題目

對應原題：LeetCode 424：Longest Repeating Character Replacement

給定只含大寫英文字母的字串 s 與整數 k。最多替換 k 個字元後，回傳可變成同一個字母的最長連續子字串長度。

例如 "AABABBA"、k = 1 的答案是 4。可把其中一個 B 換成 A，得到長度 4 的連續片段。

暴力解與瓶頸

可以枚舉每一個起點與終點，持續累計該片段裡各字母的次數。若片段長度減掉最高出現次數不超過 k，它就是有效答案。

這樣共有 O(n²) 個連續片段。即使每次更新頻率只花固定時間，總時間仍是 O(n²)。字母只有 26 種時，計數表是固定大小，額外空間是 O(1)。

我這次寫的 sliding window 解法

這就是可用的最佳漸近解。不需要改成另一種演算法，只要把視窗規則講清楚。

function characterReplacement(s: string, k: number): number {
  const map: Record<string, number> = {};
  let longest = 0;
  let maxFreq = 0;
  let p1 = 0;

  for (let p2 = 0; p2 < s.length; p2 += 1) {
    map[s[p2]] = (map[s[p2]] ?? 0) + 1;
    maxFreq = Math.max(maxFreq, map[s[p2]]);

    if (maxFreq + k < p2 - p1 + 1) {
      map[s[p1]] -= 1;
      p1 += 1;
    }

    longest = Math.max(longest, p2 - p1 + 1);
  }

  return longest;
}

p1 和 p2 表示目前視窗的左右邊界。map 記錄視窗內每個字母的次數，maxFreq 記錄目前為止看過的最高單一字母頻率。

若視窗長度是 p2 - p1 + 1，要把整段變成同一個字母，最少替換數是：

windowLength - maxFreq

當它大於 k，這段視窗太長，左指標右移一格並扣除離開字元的次數。程式裡的條件：

maxFreq + k < p2 - p1 + 1

和 windowLength - maxFreq > k 完全相同。

為何 maxFreq 不必倒退

左指標移動後，原本頻率最高的字母可能已不再那麼多，所以 maxFreq 可能比目前視窗的真正最高頻率大。這個做法仍正確。

先看縮小視窗的時機。若 windowLength - maxFreq > k，連歷史上最高的頻率都無法把這個視窗湊成同一個字母，真正的最高頻率只會更小，因此一定要移動左指標。

反過來說，歷史值偏大時，程式可能暫時保留一個目前不完全有效的視窗。但它不會把答案算得太大。某個更長的視窗第一次出現時，maxFreq 還對應到視窗裡的實際次數，否則左指標早已在它變長前縮小視窗。後來的歷史值只會保留已出現過的長度，不會創造超過最佳答案的新長度。

這也說明為何這裡用一次 if 就夠。每回合右指標只加入一個字元，windowLength - maxFreq 最多增加一；若超過 k，左指標移動一次就能恢復這個判斷式的界線。

正確性與複雜度

每回合都把 s[p2] 加入視窗。若條件失效，就移除唯一一個最左側字元。p1 只向右，p2 也只向右，兩個指標各走最多 n 次，因此時間是 O(n)。

LeetCode 的限制是大寫英文字母，計數表最多 26 格，所以額外空間是 O(1)。若題目改成任意字元集，雜湊表空間應寫成 O(min(n, c))，c 是可出現字元數。

最小驗證

import assert from "node:assert/strict";

assert.equal(characterReplacement("AABABBA", 1), 4);
assert.equal(characterReplacement("ABAB", 2), 4);
assert.equal(characterReplacement("ABBB", 2), 4);
assert.equal(characterReplacement("ABCDE", 0), 1);
assert.equal(characterReplacement("AAAA", 0), 4);

k = 0 很適合測試視窗條件。這時不能替換，答案只能是原字串中最長的連續相同字母。

常見陷阱

• 每次左指標移動都重新掃描整個視窗找最高頻率。答案仍可能正確，但失去單次走訪的好處。
• 把 maxFreq 當成目前視窗的精確最高頻率。這份程式把它當歷史上限，刻意不倒退。
• 把 if 改成迴圈後又在迴圈內重算最高頻率。這是另一種解法，但不需要用在這個條件受限的版本。
• 忽略 k = 0 或全字串同字母的邊界案例。

可遷移的思路

可變長 sliding window 先把「目前視窗是否可接受」寫成一個可遞增維護的條件。這題的條件是需要替換的數量不超過 k。加入右側字元後才檢查，失效時只移動左側到足夠的位置，不重建視窗。

補充影片

• YouTube Shorts：sliding window 解題說明

外部參考連結

• LeetCode 424：Longest Repeating Character Replacement
• Node.js：assert.equal()