Topic: Learning notes

LeetCode 424: Longest Repeating Character Replacement in TypeScript

Keep the submitted frequency-counting sliding-window solution and explain why maxFreq can retain its historical maximum.

The confusing part of this problem is that maxFreq does not decrease when the left side of the window moves. That value can look stale. Keeping the historical maximum is what lets both pointers move in one direction.

Problem

Original problem: LeetCode 424: Longest Repeating Character Replacement

Given a string s of uppercase English letters and an integer k, return the longest contiguous substring that can consist of one repeated letter after at most k replacements.

For "AABABBA" and k = 1, the answer is 4. One B can be replaced with A to make a contiguous run of four characters.

Brute force and its limit

Enumerate every start and end position, while counting letters in that interval. An interval is valid when its length minus its highest letter frequency is at most k.

There are O(n²) contiguous intervals. Even if updating the frequency count takes constant time, the total time remains O(n²). With a 26-letter alphabet, the counter has fixed size and uses O(1) auxiliary space.

My submitted sliding-window solution

This is already the best asymptotic solution. It does not need a different algorithm, only a precise explanation of the window rule.

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 and p2 are the window bounds. map stores each letter count in the window. maxFreq stores the highest count for one letter seen so far.

For a window of length p2 - p1 + 1, the fewest replacements needed to make all its letters equal is:

windowLength - maxFreq

When that value exceeds k, the window is too wide. Move the left pointer once and decrement the count of the letter that left the window. The code condition:

maxFreq + k < p2 - p1 + 1

is equivalent to windowLength - maxFreq > k.

Why maxFreq does not need to decrease

After moving the left pointer, the most frequent letter may no longer appear maxFreq times in the current window. maxFreq can therefore be higher than the exact current maximum. The algorithm is still correct.

If windowLength - maxFreq > k, even the historical maximum cannot make the window valid. The exact current maximum can only be lower, so the left pointer must move.

When the historical value is too high, the code may temporarily retain a window that is not currently valid. It still cannot overstate the answer. When a longer length first appears, maxFreq still matches an actual count in that window. Otherwise the left pointer would have shrunk the window before it grew. Later historical values only preserve a length already seen, so they cannot create a length above the optimum.

This also explains the single if. Each iteration adds one character at the right, so windowLength - maxFreq can increase by at most one. If it exceeds k, moving the left pointer once restores the boundary for this historical-maximum check.

Correctness and complexity

Each iteration adds s[p2] to the window. If the condition fails, it removes one leftmost character. p1 and p2 each move right at most n times, so time complexity is O(n).

LeetCode constrains input to uppercase English letters. The counter has at most 26 entries, so auxiliary space is O(1). For an arbitrary character set, a hash map would use O(min(n, c)) space, where c is the number of possible characters.

Minimal verification

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 is a useful boundary case. No letters can change, so the answer must be the longest existing run of one letter.

Common mistakes

• Recompute the highest frequency by scanning the full window whenever the left pointer moves. It may remain correct, but it loses the one-pass benefit.
• Treat maxFreq as the exact maximum of the current window. This code deliberately uses a historical upper bound.
• Change if to a loop and recompute the maximum inside it. That is a different valid approach, but it is unnecessary for this constrained version.
• Skip k = 0 or an input made of one repeated letter.

Transferable idea

For a variable-length sliding window, write a condition that says whether the current window is acceptable and can be maintained as the window grows. Here, the number of replacements must not exceed k. Add the right character first, then move the left side only when the condition fails. Do not rebuild the window.

Supplementary video

• YouTube Shorts: sliding-window explanation

References

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