Longest Repeating Character Replacement

mediumSliding Window39 stepsJava · Python · C++

You may replace up to k characters to make a run of one letter. A window is fixable when length - maxCount <= k, where maxCount is the most common letter inside. Grow right; if the window becomes unfixable, slide it by one.

▶ Watch the animated trace

Traced input: s = "AABABBA", k = 1 → 4. Original problem: neetcode.io/problems/longest-repeating-substring-with-replacement

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

26 counters; maxCount never needs to decrease.

Key idea

Keep the most frequent letter and replace the rest: cost = window - maxCount.
When cost exceeds k, move l forward one step (the window slides instead of shrinking).
maxCount can stay stale-high: the answer only grows when a truly higher count appears.

Common mistakes

Recomputing max over 26 counts every step is fine (O(26n)) but not required.
Shrinking with a while loop is also correct; just know why the if version works.
Counting only uppercase: the problem guarantees 'A'–'Z'.

Solution

Java

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

Python

def characterReplacement(s: str, k: int) -> int:
    count = [0] * 26
    l = max_count = best = 0
    for r, c in enumerate(s):
        count[ord(c) - ord('A')] += 1
        max_count = max(max_count, count[ord(c) - ord('A')])
        if r - l + 1 - max_count > k:
            count[ord(s[l]) - ord('A')] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

C++

int characterReplacement(string s, int k) {
    int count[26] = {0};
    int l = 0, maxCount = 0, best = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        maxCount = max(maxCount, ++count[s[r] - 'A']);
        if (r - l + 1 - maxCount > k) {
            count[s[l] - 'A']--;
            l++;
        }
        best = max(best, r - l + 1);
    }
    return best;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
k covers everything Replace both Bs (or both As).	`s = "ABAB", k = 2`	`4`
k = 0 Just the longest existing run.	`s = "AABBB", k = 0`	`3`
Single character A window of 1 is always valid.	`s = "Z", k = 0`	`1`
All different Any two letters, replacing one.	`s = "ABCD", k = 1`	`2`