Longest Repeating Character Replacement

MediumSliding WindowHash TableStringSliding Window

Problem

You are given a string of uppercase letters and an integer k. You may change up to k characters anywhere in the string to any other letter. Find the length of the longest contiguous substring that can be made to consist of a single repeated letter using at most that many changes.

Example. For "ABAB" with k = 2, changing both As to B (or both Bs to A) produces "BBBB", so the answer is 4.

Key idea

Testing every substring and counting how many changes it needs is quadratic or worse. The sliding-window trick is to notice that a window of length L needs at most k changes exactly when L minus the count of its most frequent letter is at most k: the most frequent letter is kept as-is, and every other character gets changed. Expand the window's right edge while tracking letter counts, and shrink from the left whenever the window becomes invalid. A useful shortcut: it is not necessary to recompute the true maximum frequency after shrinking. Tracking only the highest frequency ever observed is enough, because the window length can only grow again once an even larger frequency appears, so a stale frequency value never makes an invalid window look valid.

Solution

function characterReplacement(s: string, k: number): number {
  const counts = new Array<number>(26).fill(0);
  const base = 'A'.charCodeAt(0);
  let start = 0;
  let maxFrequency = 0;
  let longest = 0;

  for (let end = 0; end < s.length; end++) {
    const index = s.charCodeAt(end) - base;
    counts[index]++;
    maxFrequency = Math.max(maxFrequency, counts[index]);

    // window needs more than k changes to become uniform, so shrink it
    const windowLength = end - start + 1;
    if (windowLength - maxFrequency > k) {
      counts[s.charCodeAt(start) - base]--;
      start++; // maxFrequency is intentionally left stale here
    }

    longest = Math.max(longest, end - start + 1);
  }

  return longest;
}

Complexity

  • Time: O(n). One pass with pointers, doing constant work per character since there are only 26 possible letters.
  • Space: O(1). A fixed 26-entry count array, independent of input size.

Watch out for

  • Not decrementing the tracked maximum frequency when the window shrinks is intentional, not a bug; it is what keeps the window from shrinking below the best size already found.
  • The comparison is against window length minus max frequency, not against the count of every other letter individually.
  • k can be larger than the alphabet's natural repetition needs, in which case the whole string qualifies.

Pattern

This is the sliding window with a relaxed, count-based validity rule: allowing up to k "violations" instead of zero. The same at-most-k-exceptions shape reappears in problems that bound a window by a budget of allowed changes or replacements.

Related questions