LearnDSA PatternsSliding WindowCase Study

LeetCode 424 · Medium · Sliding Window · TypeScript

Longest Repeating Character Replacement:
6 Bugs to a Clean Solution

Not a tutorial — a real debugging log. Six attempts, six distinct bugs, each one reproduced with a hand-traced example before it was fixed.

Scroll to follow the journey

The Problem

LeetCode 424 — Longest Repeating Character Replacement

Given a string s and an integer k, you can change up to k characters in the string to any other uppercase letter. Find the length of the longest substring containing only one repeating character you can get after performing at most k replacements.

Input

"ABAB", k = 2

Output

4

Input

"AABABBA", k = 1

Output

4

Input

"AAAA", k = 2

Output

4

The Journey

Attempt by Attempt

Every bug below was traced by hand against a real input — not just described.

1 Comparing Against a Fixed Anchor, Not a Frequency Map 🐛 Buggy
function characterReplacement(s: string, k: number): number {
  let i=0, j=i+1
  let max_count = 0, temp_count = k
  while(j<s.length)
   if(s[i]===s[j]) {
    max_count = Math.max(max_count, j-i)
    j++
   }
   else {
    max_count = Math.max(max_count, j-i)
    temp_count--
    if(temp_count===0) {
      i++; j=i+1
      temp_count = k
    } else j++
   }
   return max_count
};

Runs without crashing and looks reasonable — but only ever compares s[j] against the single character s[i], never tracking which character is actually most frequent in the window.

The validity condition for this problem is windowLength − (count of the MOST FREQUENT character in the window) ≤ k. This code instead checks s[i]===s[j] — a single fixed anchor character — and resets the window almost every time a different character shows up, even when the window would still be valid against its true majority character. Because the window resets on every mismatch, it can never grow past size 2.

Proof — traced by hand on real input:

characterReplacement("AABABBA", 1)
i=0,j=1: s[i]="A" === s[j]="A" → max_count=1, j=2
i=0,j=2: "A" !== "B" → max_count=2, temp_count hits 0 → reset i=1,j=2
i=1,j=2 ... i=2,j=3 ... i=3,j=4: same pattern repeats, resetting almost every step
Window never grows past size 2 because it only ever compares against s[i]
Returns 2   (WRONG — expected 4)
Fix →

Track a frequency count of every character currently in the window (a hash map), and compare the window length against the count of whichever character is most frequent — not a single fixed anchor.

2 Hash Map Added — But delete() and a Window Reset Corrupt It 🐛 Buggy
function characterReplacement(s: string, k: number): number {
  let count: Record<string, number> = {}
  let left=0, right=0, maxFreq =0;

  while(right < s.length) {
    let windowSize = right - left +1
    if(!count[s[right]]) count[s[right]] = 1
    else count[s[right]]++

    if((windowSize - count[s[right]]) <=k ){
      maxFreq = Math.max(maxFreq, windowSize)
      right++
    } else {
      delete count[s[left]]
      left++; right =left
    }
  }
  return maxFreq
};

Good instinct switching to a frequency map, but three issues at once: the validity check compares against count[s[right]] (the newest character only) instead of the true window max, delete wipes an entire count instead of decrementing it, and right = left resets the window instead of sliding it.

delete count[s[left]] removes the key entirely — if that character appeared 3 times in the window, deleting it forgets all 3, not just the one leaving. Combined with windowSize - count[s[right]] (checking only the newest character, not the true max across the whole map) and right = left throwing the window back to size 1 on every shrink, the counts get corrupted and inflate over time instead of shrinking correctly.

Proof — traced by hand on real input:

characterReplacement("AABABBA", 1)
right=2: count={A:2,B:1}. Check compares windowSize(3) against count["B"](1), not the true max(2)
3 - 1 = 2 > k → shrink: delete count["A"] wipes BOTH A's, not one → count={B:1}
right jumps back to left (right=left), discarding the window instead of sliding it
Corruption compounds on every later shrink as counts get deleted instead of decremented
Returns 5   (WRONG — expected 4, larger than any single character's true frequency allows)
Fix →

Decrement the outgoing character's count (count[s[left]]--) instead of deleting it, compare against the window's true max frequency (not just the newest character), and only ever advance left — never reset right backward.

3 delete Fixed to a Decrement — But maxFreq Tracks the Wrong Thing 🐛 Buggy
function characterReplacement(s: string, k: number): number {
  let count: Record<string, number> = {}
  let left=0, right=0, maxFreq =0;

  while(right < s.length) {
    let windowSize = right - left +1
    if(!count[s[right]]) count[s[right]] = 1
    else count[s[right]]++

    if((windowSize - maxFreq) <=k ){
      maxFreq = Math.max(maxFreq, windowSize)
      right++
    } else {
      count[s[left]]--
      left++;
    }
  }
  return maxFreq
};
// ⚠ maxFreq tracks window SIZE, not char frequency — and right never advances on shrink, so count[s[right]]++ re-counts the same index next loop

count[s[left]]-- is a real fix. But maxFreq is now being set to windowSize itself on every valid step — not the actual count of the most frequent character — and right never advances when the window is invalid.

Setting maxFreq = Math.max(maxFreq, windowSize) conflates two different concepts: the window's SIZE and the true frequency of its most common character. Those aren't the same number. Worse, in the else branch only left++ runs — right stays exactly where it was, so the very next loop iteration runs count[s[right]]++ again for that same index, double-counting a character that never actually re-entered the window.

Proof — traced by hand on real input:

characterReplacement("AABABBA", 1)
right=3: window "AABA" is genuinely valid (4-3=1≤k) but maxFreq gets set to windowSize(4), not the true char count(3)
right=4: window invalid — only left++ runs, right stays put, so count[s[right]]++ re-adds the same character next iteration
Stale, inflated maxFreq plus double-counted characters compound with every further step
Returns 7   (WRONG — expected 4, and impossible: no valid window this large exists for k=1)
Fix →

maxFreq must equal the true highest single-character count in the window (from the frequency map), never the window size. And every loop iteration must move right forward exactly once — whether the window grew or slid — so no character gets counted twice.

4 right++ Fixed — But Object.keys() and a Broken reduce() Produce NaN 🐛 Buggy
function characterReplacement(s: string, k: number): number {
  let count: Record<string, number> = {}
  let left=0, right=0, maxFreq =0;

  while(right < s.length) {
    let windowSize = right - left +1
    if(!count[s[right]]) count[s[right]] = 1
    else count[s[right]]++

    if((windowSize - maxFreq) <=k ){
      let currMaxFreq = Object.keys(count).reduce((max, obj) => max>obj)
      maxFreq = Math.max(maxFreq, currMaxFreq)
      right++
    } else {
      count[s[left]]--
      left++; right++
    }
  }
  return maxFreq
};
// ⚠ Object.keys returns characters, not counts — and the reduce callback returns a boolean, not a number → maxFreq becomes NaN

Moving right++ into both branches correctly stops the double-counting bug. But the new line computing the window's true max frequency has two separate JavaScript mistakes.

Object.keys(count) returns the CHARACTERS ('A', 'B'), not their counts (3, 2) — so the reduce is comparing letters, not numbers. On top of that, the callback (max, obj) => max > obj returns a boolean (true/false), which is not a valid accumulator value for reduce. The very first Math.max(0, 'A') call coerces 'A' to NaN, and NaN propagates through every comparison for the rest of the run.

Proof — traced by hand on real input:

characterReplacement("AABABBA", 1)
right=0: count={A:1}. Object.keys(count) = ["A"] — the CHARACTER, not its count
.reduce((max, obj) => max > obj) returns a boolean on its first comparison, not a number
maxFreq = Math.max(0, "A") → NaN (a string cannot be compared numerically)
Every check after this involves NaN, which is never ≤ k
Returns NaN   (WRONG — expected 4, not even a valid number)
Fix →

Use Object.values(count) to get the actual counts, and make the reduce callback return the accumulated maximum itself — e.g. (max, val) => Math.max(max, val) — not a comparison result.

5 Object.values() Fixed — But the Check Runs on Stale Data 🐛 Buggy
function characterReplacement(s: string, k: number): number {
  let count: Record<string, number> = {}
  let left = 0, right = 0, maxFreq = 0;

  while (right < s.length) {
    let windowSize = right - left + 1
    if (!count[s[right]]) count[s[right]] = 1
    else count[s[right]]++

    if ((windowSize - maxFreq) <= k) {
      let vals = Object.values(count)
      let currMaxFreq = vals.reduce((max, val) => Math.max(max, val), 0)
      maxFreq = Math.max(maxFreq, currMaxFreq)
      right++
    } else {
      count[s[left]]--
      left++; right++
    }
  }
  return maxFreq
};
// ⚠ the validity check runs BEFORE currMaxFreq is recalculated — it compares against last iteration's stale maxFreq

Object.values(count).reduce((max, val) => Math.max(max, val), 0) correctly computes the window's true max frequency. But it's computed INSIDE the if-block — after the validity check has already run against the OLD maxFreq from the previous iteration.

At the moment the if-condition is evaluated, count[s[right]] has already been incremented for the character just added — but maxFreq hasn't caught up yet. The check compares windowSize against a number that doesn't reflect the character that was just added, so a genuinely valid window can get rejected simply because the freshest data hasn't been folded into maxFreq yet.

Proof — traced by hand on real input:

characterReplacement("AABABBA", 1)
right=3: count becomes {A:3, B:1} after the increment — the true max frequency is now 3
But the if-check runs FIRST, still comparing against last iteration's maxFreq (2), not the fresh 3
4 - 2 = 2 > k → window "AABA" (which IS valid: 4-3=1≤1) gets incorrectly rejected and shrunk
maxFreq never gets the chance to update to 3 or higher again for the rest of the string
Returns 2   (WRONG — expected 4)
Fix →

Recompute the window's true max frequency immediately after updating the count map — BEFORE the if-check runs — so the validity check always evaluates against fresh, current-iteration data.

6 Ordering Fixed — But the Wrong Variable Gets Returned 🐛 Buggy
function characterReplacement(s: string, k: number): number {
  let count: Record<string, number> = {}
  let left = 0, right = 0, maxFreq = 0;

  while (right < s.length) {
    let windowSize = right - left + 1
    if (!count[s[right]]) count[s[right]] = 1
    else count[s[right]]++

    let vals = Object.values(count)
    let currMaxFreq = vals.reduce((max, val) => Math.max(max, val), 0)
    maxFreq = Math.max(maxFreq, currMaxFreq)

    if ((windowSize - maxFreq) <= k) {
      right++
    } else {
      count[s[left]]--
      left++; right++
    }
  }
  return maxFreq
};
// ⚠ maxFreq is the highest single-character count ever seen — not the same thing as the longest valid window length

Moving the frequency recalculation above the if-check was the missing piece — the validity logic is now fully correct. The last bug is simpler: the function returns maxFreq, but maxFreq is not the answer.

maxFreq tracks 'the highest count of any single character seen in a window so far' — a helper value used only to decide whether to grow or slide. The actual answer is the longest valid WINDOW LENGTH. Because the window's size (right − left) never decreases in this loop — it only grows (valid branch) or holds steady (invalid branch, both pointers advance) — the final value of right − left after the loop equals the largest window size ever proven valid, which is exactly the answer.

Proof — traced by hand on real input:

characterReplacement("AABABBA", 1)
right=3: currMaxFreq correctly computed as 3 BEFORE the check — window "AABA" is validated correctly this time
maxFreq settles at 3 for the rest of the loop (the true max character frequency ever found)
But the function returns maxFreq (3) — a helper value — instead of right - left (which ends at 7-3=4)
Returns 3   (WRONG — expected 4; the validity logic is now fully correct, only the return value is wrong)
Fix →

Return right - left, not maxFreq. The window-size invariant (never shrinks, only grows or slides) is what makes right - left equal the correct answer at the end of the loop.

Interactive

Window Visualizer

Watch the non-shrinking window slide on "AABABBA", k=1.

[0] [1] [2] [3] [4] [5] [6] A A B A B B A L R size=1 maxFreq=1 k=1

right=0 'A': count[A]=1, maxFreq=1. size(1)-maxFreq(1)=0≤k(1) → grow.

in window final window

Lessons Learned

Key Takeaways

🎯

A single anchor comparison can't detect a shifting majority character

Comparing s[i] to s[j] only tests against one fixed character. The real condition depends on whichever character is most frequent in the window right now — and that can change as the window grows.

🗑️

delete wipes an entire key — it doesn't decrement it

Removing one occurrence of a repeating character from a window needs count[char]--. delete count[char] forgets every occurrence still inside the window, not just the one that left.

🔁

Never shrink the window — slide it

On an invalid window, advancing both left and right by one preserves the window's size while testing a new position. Jumping right back to left throws away a length you already proved was achievable.

⏱️

A validity check needs this iteration's freshest data

Computing a value only after (or inside) the check that depends on it means the check runs against stale, last-iteration data. Update first, then check — not the other way around.

🎁

Track a helper value; return the actual answer

maxFreq (the highest single-character count seen) is a means to an end, not the final answer. The invariant that window size never decreases is what lets right - left double as the correct return value.

🕳️

Object.keys() gives you keys, not values — and reduce must return the accumulator

Object.keys(count) returns characters, not counts; Object.values(count) is what you want. And a reduce callback must return the next accumulator value (Math.max(max, val)), not a comparison result like max > val.

Final Result

The Verified Solution

Sliding window + frequency map — grow the window while it's valid, slide (never shrink) when it isn't.

Final — Attempt 7
// O(N) time, O(1) space (26-letter alphabet) — sliding window + frequency map
function characterReplacement(s: string, k: number): number {
  const count: Record<string, number> = {};
  let left = 0, right = 0, maxFreq = 0;

  while (right < s.length) {
    const windowSize = right - left + 1;
    count[s[right]] = (count[s[right]] ?? 0) + 1;

    // Recompute the current window's true max frequency BEFORE checking validity
    maxFreq = Math.max(maxFreq, count[s[right]]);

    if (windowSize - maxFreq <= k) {
      right++; // window grows
    } else {
      count[s[left]]--;
      left++; right++; // window slides — never shrinks
    }
  }

  // The window never shrinks below its best size, so its final size IS the answer
  return right - left;
}

// "AABABBA", k=1 → 4 (replace one 'B' to get "AAAA" / "ABAA")
console.log(characterReplacement("AABABBA", 1)); // → 4

Note: computing maxFreq incrementally from count[s[right]] (shown above) avoids rescanning the whole map every step. Attempt 6's Object.values(count).reduce(...) version still works too — since the alphabet is capped at 26 uppercase letters, that rescan is O(26) per step, which is still O(N) overall, just with a larger constant.

Solution Time Space Verified
Sliding Window + Frequency Map (Attempt 7) Verified ✓ O(N) O(1) Traced against every failing case above, incl. "AABABBA", k=1

Reuse This

Template: Non-Shrinking Sliding Window

The generic shape behind this solution — a subtler variant where the window only ever grows or slides, never shrinks.

Pseudocode
function nonShrinkingSlidingWindow(items, k):
    count = emptyFrequencyMap()
    left = 0
    maxFreq = 0

    for right in 0..items.length - 1:
        count[items[right]]++
        maxFreq = max(maxFreq, count[items[right]])   // best single-key count seen in ANY window so far

        if (right - left + 1) - maxFreq > k:
            // window invalid → slide, don't shrink: drop left, window size stays the same
            count[items[left]]--
            left++

    return items.length - left   // final window size is the answer — it never shrinks below its best

When to reach for this

"Longest window with at most K changes/replacements allowed" problems, where the answer only ever grows.

The trap this journey hit

maxFreq is recomputed before the validity check every iteration — checking it against a stale value from the previous loop silently breaks the answer.

Test Yourself

Quiz: Check Your Understanding

Question 1 of 12 Score: 0
Why does this problem call for a sliding window with a frequency map, rather than checking every substring directly? basic

Keep Learning

Bugs are part of the process 🎉

Six real bugs, six real fixes — that's what getting to a correct Sliding Window solution actually looks like.