Longest Repeating Character Replacement

Problem in Plain English

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 turned into a run of one repeated letter.

Problem Statement

Given a non-empty string s of uppercase English letters and an integer k, you may replace at most k characters with other uppercase English letters. Return the maximum length of a contiguous substring that can contain just one repeated letter after those changes. Return a length, not the changed string, and do not actually modify s.

For a candidate window of length L with most frequent letter count F, keeping that letter and replacing all others costs exactly L - F changes. The window is genuinely feasible when L - F <= k.

Constraints

1 <= s.length <= 10^5
s consists of only uppercase English letters.
0 <= k <= s.length

Examples

Example 1

Input: s = "ABAB", k = 2
Output: 4

Replace the two A letters with B letters (or vice versa) to get "BBBB", a run of length 4.

Example 2

Input: s = "AABABBA", k = 1
Output: 4

Replace the middle A with B to get "AABBBBA", which contains the run "BBBB" of length 4.

Example 3

Input: s = "ABAB", k = 0
Output: 1

No replacements are allowed, and adjacent letters differ, so only a single-letter substring is uniform.

Example 4

Input: s = "AAAA", k = 0
Output: 4

The full string is already one repeated letter and costs zero replacements.

Example 5

Input: s = "ABCDE", k = 5
Output: 5

Keeping any one letter requires replacing four positions, within the allowed budget. The answer cannot exceed the original length.

Intuition

Keep the letter already occurring most often in a candidate substring, since every other letter costs one replacement. In ABAB, A and B each occur twice: keeping either one changes two of the four positions, so k = 2 allows the full length 4. Extending a window may create a better answer; removing from its left lets the search continue without restarting. The optimized algorithm remembers a historical frequency bound to search for a length, so its current window need not always be genuinely feasible.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Try every starting index and extend its substring with fresh letter counts. The maximum count is exact for this growing substring. Stop a start as soon as its required replacements exceed k, because extending further cannot reduce that requirement.

Step-by-Step Logic

Set best to zero. For each start i, create 26 zero counters and set maxFreq = 0. Extend end j from i toward the end, adding one count at a time.
Update maxFreq from the newly added letter. Since this fixed-start window only grows, the maximum never decreases and is the exact current top frequency.
If (j - i + 1) - maxFreq <= k, update best from the length. Otherwise break this start's inner scan and move to the next start.
Example 1 from i = 0 examines A, AB, ABA, ABAB, with replacement costs 0, 1, 1, 2. All fit k = 2, and best becomes 4.
Repeat for starts 1, 2, 3 using fresh counts. Their shorter substrings do not improve 4; return best. The table lists all ten windows checked.

Why It Works

Each feasible answer starts at one enumerated index. Within that start, counts and maxFreq exactly describe the candidate, so length minus maxFreq is precisely its minimum replacement cost. Adding one character increases length by one and increases the top frequency by at most one; the required cost therefore cannot decrease. Once a candidate exceeds k, no longer candidate from the same start can qualify, so breaking loses no answer. Taking the best over all starts covers every possible maximum.

Dry Run

Brute Force: variable states at each step
start,end	Added letter	Window	Counts after	Exact maxFreq	Changes needed	Best after
`0,0`	`A`	`A`	`{"A":1}`	`1`	`0`	`1`
`0,1`	`B`	`AB`	`{"A":1,"B":1}`	`1`	`1`	`2`
`0,2`	`A`	`ABA`	`{"A":2,"B":1}`	`2`	`1`	`3`
`0,3`	`B`	`ABAB`	`{"A":2,"B":2}`	`2`	`2`	`4`
`1,1`	`B`	`B`	`{"B":1}`	`1`	`0`	`4`
`1,2`	`A`	`BA`	`{"B":1,"A":1}`	`1`	`1`	`4`
`1,3`	`B`	`BAB`	`{"B":2,"A":1}`	`2`	`1`	`4`
`2,2`	`A`	`A`	`{"A":1}`	`1`	`0`	`4`
`2,3`	`B`	`AB`	`{"A":1,"B":1}`	`1`	`1`	`4`
`3,3`	`B`	`B`	`{"B":1}`	`1`	`0`	`4`
Finish	none	all starts checked	reset between starts	none	none	return `4`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

Let n be the string length. A uniform string makes all n(n + 1)/2 candidates feasible, so early termination does not remove the O(n^2) worst case. Each extension performs constant work, and only 26 counters plus indices and a few integers are stored, giving O(1) extra space.

Code

Solution.java

1class Solution {2    public int characterReplacement(String s, int k) {3        int maxLength = 0;4        int n = s.length();5        for (int i = 0; i < n; i++) {6            int[] counts = new int[26];7            int maxFreq = 0;8            for (int j = i; j < n; j++) {9                int c = s.charAt(j) - 'A';10                counts[c]++;11                if (counts[c] > maxFreq) {12                    maxFreq = counts[c];13                }14                if ((j - i + 1) - maxFreq <= k) {15                    if (j - i + 1 > maxLength) {16                        maxLength = j - i + 1;17                    }18                } else {19                    break;20                }21            }22        }23        return maxLength;24    }25}

Hints

Hint 1

For a chosen substring, which existing letter should stay unchanged to minimize the number of replacements?

Hint 2

If length is L and its most frequent letter occurs F times, the exact replacement cost is L - F. Counts over the fixed 26-letter alphabet make this inexpensive.

Hint 3

A linear length search can retain the largest frequency seen instead of recomputing it after removals. Treat that value as historical, not as proof that every currently retained window is feasible.

Edge Cases

One character returns 1 for either permitted k value. Empty strings are outside this problem's public constraints.
With k = 0, the answer is the longest existing contiguous run; ABAB returns 1.
Uniform input such as AAAA returns 4 even with zero budget. It is also a quadratic worst case for the baseline.
A budget equal to n allows the entire string, although at most n - 1 replacements are actually needed.
AABABBA with k = 1 returns 4 even though its final retained ABBA window requires two changes. The recorded length has an earlier feasible witness.

Common Mistakes and Interview Tips

Treating historical maxFreq as the exact maximum after a removal can falsely label an infeasible current window valid. It is a bound used to search for a length.
Returning the final substring from this length-only optimization may return an infeasible example; the contract asks only for a length.
Decrementing maxFreq to the outgoing character's new count is not a correct exact-maximum update. Recomputing all 26 counters is a valid alternative, but requires the exact-window shrink rule and a different proof.
Using a strict comparison that rejects exactly k replacements drops valid windows. The cost is permitted when it is <= k.
Interview tip: derive the exact length-minus-frequency rule before discussing historical counts. Explain why an old record may be retained without a feasible current window and why a new record still has a witness.

Key Takeaway

A budgeted window can use a historical frequency bound when the requested output is a maximum length and record growth has a feasible witness. Distinguish this optimization from maintaining an exactly valid current substring.