Typorithm · medium

Longest Repeating Char Replacement

longest-repeating-character-replacementsliding-windowvariable-windowfrequencyk-budget

Saved on this device

Full lesson · 7 learning steps Open any exercise for focused practice

Step 1 of 7 · intro card

Learn Longest Repeating Char Replacement

Sliding Window

Keep a window where (length minus most-frequent count) <= k, since those are exactly the characters you must replace.

With k replacements, a window is valid if all but the most common character can be changed to match it.

That replacement cost is window length minus the highest character frequency.

Expand right, update the frequency, and shrink left whenever the cost exceeds k.

Cost = window length - maxFreq.

Valid while cost <= k.

Shrink left when over budget.

function characterReplacement(s, k) {
  const count = new Map();
  let left = 0;
  let maxFreq = 0;
  let best = 0;

  for (let right = 0; right < s.length; right += 1) {
    const ch = s[right];
    count.set(ch, (count.get(ch) ?? 0) + 1);
    maxFreq = Math.max(maxFreq, count.get(ch));

    while (right - left + 1 - maxFreq > k) {
      count.set(s[left], count.get(s[left]) - 1);
      left += 1;
    }

    best = Math.max(best, right - left + 1);
  }

  return best;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Count with ?? 0

Nullish coalescing defaults a missing count to 0 before incrementing.

count.set(ch, (count.get(ch) ?? 0) + 1)

2. Most common char

Track the highest single-character frequency in the window.

maxFreq = Math.max(maxFreq, count.get(ch))

3. Replacements over budget

Window size minus the dominant count is how many chars must change.

while (right - left + 1 - maxFreq > k) {

4. Shrink left

Drop the leftmost character's count as the window shrinks.

count.set(s[left], count.get(s[left]) - 1)

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.