Longest Repeating Character Replacement

Replace at most k letters so the longest possible substring has one repeated letter.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Longest Repeating Character Replacement: Keep a candidate length while window length - historical max frequency stays within k = 1.

Input and goalReplace at most `k` letters so the longest possible substring has one repeated letter.

Initialize the scanFor "AABABBA" with k = 1, start L = 0, largest_count = 0, best = 0, and inspect R = 0.

LRA0A1B2A3B4B5A6

rangeempty before reading index 0budgetk = 1best0

saved stateempty

Recognize it

Use it for a longest contiguous span that may change at most k items into one repeated value; window length minus its dominant frequency is the required edit count.

Keep true

After each shrink, window length is at most largest_count + k, where largest_count is the greatest frequency seen while expanding. best is the greatest retained candidate length seen so far.

Reuse it

When edits can homogenize a window, rewrite validity as window size minus the best keepable group. A monotone summary can be enough for maximizing length even when it overestimates a later window frequency.

Pattern: Sliding window with counts.

Simple idea: Keep the most common letter. Every other letter in the window needs one replacement. The window is valid when:

window length - largest letter count <= k

from collections import defaultdict

def character_replacement(text: str, replacements: int) -> int:
   counts: dict[str, int] = defaultdict(int)
   left = 0
   largest_count = 0
   best = 0

   for right, char in enumerate(text):
      counts[char] += 1
      largest_count = max(largest_count, counts[char])

      while right - left + 1 - largest_count > replacements:
         counts[text[left]] -= 1
         left += 1

      best = max(best, right - left + 1)

   return best

Cost: $O(n)$ time and $O(k)$ space.