Longest Repeating Character Replacement

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given a string of uppercase letters and an integer k, you may change at most k characters to any other uppercase letter. Return the length of the longest substring that can be made of a single repeated letter.

    A sliding window problem with one clever observation: a window is fixable exactly when its length minus the count of its most common letter is at most k. Variants change the alphabet or ask for the longest run of 1s with k flips, and the same window answers them all. Original problem: LeetCode 424.

    Example

    In BBACBB only the A and the C differ from B, so two changes make six B's in a row.
    In BBACBB only the A and the C differ from B, so two changes make six B's in a row.
    s = "ABBACBB", k = 2
    Output: 6          # "BBACBB" -> change A and C -> "BBBBBB"
    s = "ABBACBB", k = 1
    Output: 3          # e.g. "ABB" -> "BBB"

    Constraints (assumed)

    • 1 ≤ n ≤ 10⁵; uppercase English letters; 0 ≤ k ≤ n.

    What this question tests

    • Turning "can this substring be fixed?" into a window condition: length − maxFreq ≤ k.
    • A clean grow-right, shrink-left window with letter counts.
    • Understanding why maxFreq doesn't have to decrease when the window shrinks.

    Questions to ask first

    1. Which characters can appear? (Here: 26 uppercase letters, so a fixed-size count array works.)
    2. Must I use all k changes? (No; at most k.)
    3. Can k be 0 or at least n? Then the answer is the longest existing run, or n.
    4. Do you want the substring or its length? (Here: the length.)