Longest Repeating Character Replacement

MediumSliding Window · Majority Count🧩 Sliding Window LeetCode #424 ↗Updated Oct 30, 2026

Problem

You get a string s of uppercase English letters and a budget k. You may overwrite at most k characters with any letter you like. Return the length of the longest contiguous block that can be made to consist of a single repeated letter.

Inputs = "ABAB", k = 2Output4 (rewrite both B's)

Inputs = "AABABBA", k = 1Output4 (e.g. "AABA" → "AAAA")

Inputs = "ABCD", k = 0Output1

1 ≤ n ≤ 10⁵ · s has uppercase letters only · 0 ≤ k ≤ n

Try it yourself

Java

class Solution {
    public int characterReplacement(String s, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A window is fixable iff

length - (count of its most common letter) ≤
        k

. Slide a window; the answer can only grow when that top count grows, so the top count never needs to be decreased.

PatternSliding Window

Instinct Longest, shortest or count of contiguous subarrays/substrings meeting a rule? Grow a window on the right, shrink it on the left, never step back.

Memory hack Move like a caterpillar - the head stretches forward to grab, the tail pulls up only when the body breaks the rule.

Open the Sliding Window guide →

Approaches

Brute ForceEvery Start, Extend with Running Counts

Time O(n²)Space O(1)

For each start i, extend the end j one letter at a time while updating 26 counts and the running maximum count. Whenever (j - i + 1) - maxCount ≤ k, the block can be made uniform by rewriting the minority letters.

Java

public int characterReplacement(String s, int k) {
    int n = s.length(), best = 0;
    for (int i = 0; i < n; i++) {
        int[] count = new int[26];
        int maxCount = 0;
        for (int j = i; j < n; j++) {
            maxCount = Math.max(maxCount, ++count[s.charAt(j) - 'A']);
            if (j - i + 1 - maxCount <= k) best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

Simple and correct, but tries all n²/2 substrings.

BetterSliding Window, Recompute the Max

Time O(26 · n)Space O(1)

Grow the window to the right. While it needs more than k changes, drop letters from the left. The most common count is recomputed by scanning all 26 counters, so the window is always exactly valid.

Java

public int characterReplacement(String s, int k) {
    int[] count = new int[26];
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        count[s.charAt(right) - 'A']++;
        while (right - left + 1 - maxOf(count) > k) {
            count[s.charAt(left) - 'A']--; // shrink until fixable
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

private int maxOf(int[] count) {
    int m = 0;
    for (int c : count) m = Math.max(m, c);
    return m;
}

Linear in n, but pays a 26-step scan on every check.

OptimalNon-Shrinking Window with Stale Max

Time O(n)Space O(1)

Keep maxFreq = the highest single-letter count ever seen in a window, and never lower it. A longer answer needs a bigger maxFreq, so a stale value only stops the window from growing — it then just slides right by one, keeping its size.

Java

public int characterReplacement(String s, int k) {
    int[] count = new int[26];
    int left = 0, maxFreq = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        maxFreq = Math.max(maxFreq, ++count[s.charAt(right) - 'A']);
        if (right - left + 1 - maxFreq > k) {
            count[s.charAt(left) - 'A']--; // slide, don't shrink
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Dry runs = "AABABBA", k = 1

l leftr right changed

r=1
A
l
A
r
B

A

B

B

A

maxFreq 2, best 2
r=2
A
l
A

B
r
A

B

B

A

3-2=1 ok, best 3
r=3
A
l
A

B

A
r
B

B

A

maxFreq 3, best 4
r=4
A

A
l
B

A

B
r
B

A

5-3=2 > 1: slide
r=5
A

A

B
l
A

B

B
r
A

B=3, still 2 > 1: slide
r=6
A

A

B

A
l
B

B

A
r
slide; answer 4 ✔

One pass, O(1) work per step; the window size equals the best answer so far.

Pro tip

Because the window never shrinks, the answer is also simply n - left at the end.

At a glance

Level	Approach	Time	Space
Brute Force	Every Start, Extend with Running Counts	`O(n²)`	`O(1)`
Better	Sliding Window, Recompute the Max	`O(26 · n)`	`O(1)`
Optimal	Non-Shrinking Window with Stale Max	`O(n)`	`O(1)`

Common pitfalls

Counting distinct letters instead of length - maxCount as the cost.
Believing the stale maxFreq is a bug — it is safe because it never inflates the answer.
Moving left without decrementing the count of the letter that leaves the window.

Interview tips

Phrase the validity test first: changes needed = length - most frequent count.
Present the O(26n) window, then justify the never-decreasing maxFreq trick.
Mention the alternative: run a “at most k non-X” window for each letter X.

Pattern

Sliding window with a budget → longest range where the number of “bad” items is at most k.

My notes saved in this browser