Longest Repeating Character Replacement

MediumSliding WindowNeetCode 150MidOpen on LeetCodeUpdated Sep 21, 2026

You're given a string s of uppercase English letters and an integer k. You may change any character of s to any other uppercase letter, at most k times in total. Return the length of the longest substring (contiguous) that could consist of a single repeated letter after those changes. You don't have to use all k changes, and with k = 0 the answer is the longest existing run of one letter.

Examples

s = "ABAB", k = 2 returns 4

Change both A's to B (or both B's to A) and the whole string becomes one letter, so the answer is the full length, 4.

s = "AABABBA", k = 1 returns 4

Changing the highlighted A gives four B's in a row.

Change the A at index 3 to B and indices 2 to 5 read "BBBB". No substring of length 5 works, because each one contains two copies of its less common letter.

Constraints

1 <= s.length <= 10^5
0 <= k <= s.length

Hints

Hint 1

If you could change up to k characters, what makes a range 'valid'?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

A window can be made uniform when its length minus the count of its most frequent letter is at most k, since the other letters are the ones to change. Extend right, updating the letter counts and maxCount. If the window becomes invalid, slide left forward by one, so the window never shrinks. maxCount is never decreased: a stale value only stops the window from growing, and the best length improves only when a truly higher count appears.

Time

O(n)

Space

O(1)

Pitfall

A window's cost is its length minus the count of its most common letter. Using the count of the letter just added (count[s[right]]) instead of the running maximum rejects valid windows, like "AAAB" with k = 1 when the B arrives.

Solutions

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

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