Frontend Beauty
ESC

Type to search the knowledge base.

Longest Repeating Character Replacement

Longest substring replaceable into one character with ≤ k swaps — sliding window, max-frequency tracking, O(n).

intermediate3 min read
  • dsa
  • sliding-window
  • interview
  • Google
  • Meta

The problem

String s of uppercase letters, integer k. You may replace any character with another at most k times. Return the length of the longest substring containable of the same letter after those replacements.

s = "ABAB", k = 2 → 4  // replace both A's or both B's
s = "AABABBA", k = 1 → 4 // e.g. "AABA" → "AAAA"

Core inequality

In a window, let maxf = count of the most frequent character.
You need windowLen - maxf replacements to make the window uniform.
Valid iff windowLen - maxf ≤ k.

Brute

For every window, count freq, check inequality. O(n² · Σ).

Optimal sliding window

Expand right. Track counts and maxf. While invalid, advance left and decrement counts. Answer is max window length seen.

function characterReplacement(s: string, k: number): number {
  const cnt = new Array<number>(26).fill(0);
  let left = 0;
  let maxf = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    const ri = s.charCodeAt(right) - 65;
    cnt[ri]++;
    maxf = Math.max(maxf, cnt[ri]);

    // shrink until valid
    while (right - left + 1 - maxf > k) {
      cnt[s.charCodeAt(left) - 65]--;
      left++;
      // maxf may be stale — still correct for max length (see note)
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}
Time O(n)
Space O(1) alphabet

Stale maxf note

When shrinking, some solutions don’t recompute maxf. That’s OK for maximum window length: a stale (too large) maxf only makes the while condition stricter later; you never accept a longer invalid window, and any better answer still forces a larger true maxf when expanded. Recomputing maxf each shrink is clearer if you’re unsure:

// safer shrink
while (right - left + 1 - maxf > k) {
  cnt[s.charCodeAt(left) - 65]--;
  left++;
  maxf = Math.max(...cnt); // O(26)
}

Walk "AABABBA", k=1

Windows grow; when need >1 replace, left moves. Best length 4.

Edge cases

  • k = 0 → longest run of identical chars
  • k ≥ n → n
  • All unique letters
  • Single character string

Common mistakes

  • Using total unique count instead of max frequency
  • Fixed window size only
  • Lowercase char codes without offset care

Interview delivery

  1. Window valid iff len − maxf ≤ k.
  2. Sliding expand/shrink.
  3. Optional stale maxf discussion.
  4. O(n).
  5. Edge k=0.

Mental model

Sliding window of candidates for the final monochrome substring. The bottleneck is how many characters aren’t the mode of the window — those need replacements.

Why the answer is a length not a string

Problem only asks length. You don’t need to materialize replacements. If asked for any valid substring, store bestL/bestR when updating best.

  • Longest substring with ≤ k distinct characters
  • Longest substring without repeating (k=0 special flavor)
  • Min window covering a charset

Same expand/shrink skeleton, different validity predicate.

Out-loud answer

“Window valid if length − maxFrequency ≤ k. Expand right, shrink left while invalid, track max length. O(n) with fixed alphabet counts. k=0 reduces to longest run.”

Further reading