#424 Longest Repeating Character Replacement

frequently reported atBloomberg Amazon Google Microsoft ByteDance / TikTok Meta

the problem

In plain words

s has uppercase letters. You may change at most k characters to any letter. Return the length of the longest substring that can be made of one repeated letter.

in s = "ABAB", k = 2

out 4

Change both A's (or both B's).

in s = "AABABBA", k = 1

out 4

Change the B in "AABA" to get "AAAA".

1 ≤ s.length ≤ 10⁵
Uppercase English letters
0 ≤ k ≤ s.length

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternSliding window (variable size)Frequency counting

A window can become one letter if length − (count of its most common letter) ≤ k. Keep the most common letter, replace the rest.

solutions

From brute force to optimal

For each start, extend the end while updating a count array and the max count.

For each i: reset count[26], maxFreq.
For each j ≥ i: update count and maxFreq.
If (j − i + 1) − maxFreq ≤ k, record the length.

timeO(n²)

n starts × up to n ends, O(1) work each.

spaceO(1)

A 26-slot array.

java

1class Solution {2    public int characterReplacement(String s, int k) {3        int best = 0;4        for (int i = 0; i < s.length(); i++) {5            int[] count = new int[26];6            int maxFreq = 0;7            for (int j = i; j < s.length(); j++) {8                maxFreq = Math.max(maxFreq, ++count[s.charAt(j) - 'A']);9                int len = j - i + 1;10                if (len - maxFreq <= k) best = Math.max(best, len); // replace all the others11            }12        }13        return best;14    }15}

Grow right, track the highest count seen; shrink while the window needs more than k replacements.

count[26], left = 0, maxFreq = 0.
Add s[right]; maxFreq = max(maxFreq, its count).
While (right − left + 1) − maxFreq > k: remove s[left], left++.
best = max(best, right − left + 1).

timeO(n)

Each index enters once and leaves at most once.

spaceO(1)

26 counters.

java

1class Solution {2    public int characterReplacement(String s, int k) {3        int[] count = new int[26];4        int left = 0, maxFreq = 0, best = 0;5        for (int right = 0; right < s.length(); right++) {6            maxFreq = Math.max(maxFreq, ++count[s.charAt(right) - 'A']);7            while (right - left + 1 - maxFreq > k) {   // too many to replace8                count[s.charAt(left) - 'A']--;9                left++;10            }11            best = Math.max(best, right - left + 1);12        }13        return best;14    }15}

sim

Dry run

loading simulation…

java

1class Solution {2    public int characterReplacement(String s, int k) {3        int[] count = new int[26];4        int left = 0, maxFreq = 0, best = 0;5        for (int right = 0; right < s.length(); right++) {6            maxFreq = Math.max(maxFreq, ++count[s.charAt(right) - 'A']);7            while (right - left + 1 - maxFreq > k) {   // too many to replace8                count[s.charAt(left) - 'A']--;9                left++;10            }11            best = Math.max(best, right - left + 1);12        }13        return best;14    }15}

in the room

How to say it in the interview

talk track

Derive the validity rule out loud: "replacements needed = length − most frequent count".
Expect the question "why don't you decrease maxFreq when shrinking?" — a stale maxFreq never creates a longer false answer.
If unsure, recomputing maxFreq from the 26 counts each step is still O(26·n) = O(n).

traps

Indexing with c - 'a' — the letters are uppercase, so use c - 'A'.
Recomputing the window's true max count on every shrink — correct but unnecessary; the stale maxFreq is enough.

what they ask next

Follow-ups

Max Consecutive Ones III (LC 1004)?

The same problem on a binary array: "replacements" are the zeros in the window.

before you submit

Edge cases to test

k = 0: the answer is the longest run of one letter as it stands.
k ≥ length: the whole string can become one letter.
Uppercase input: index with c - 'A'; c - 'a' goes negative.
All letters different: the answer is min(n, k + 1).

practise next