DSAPrep
MediumSliding Window

Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one A in the middle with B to form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of only uppercase English letters.
  • 0 <= k <= s.length
View original on LeetCode ↗

The brute force checks every substring and counts how many characters would need to change. The optimal approach reframes the question: a window of length L is achievable if L - (count of its most frequent character) <= k, since that difference is exactly how many characters need replacing. So we grow a sliding window, track the highest character frequency seen inside it, and only shrink when the window can no longer be fixed with k replacements.

Brute Force

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

For every window [i, j], count character frequencies and check if (j - i + 1) - max_frequency <= k.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        n = len(s)
        best = 0
        for i in range(n):
            count = {}
            max_freq = 0
            for j in range(i, n):
                count[s[j]] = count.get(s[j], 0) + 1
                max_freq = max(max_freq, count[s[j]])
                if (j - i + 1) - max_freq <= k:
                    best = max(best, j - i + 1)
        return best

Why it’s slow: there are O(n²) windows, and recomputing the character counts and max frequency for each one (even incrementally) still means O(n) windows per starting index — O(n²) total, with an extra constant factor for tracking frequencies of up to 26 letters.

Sliding Window (Max Frequency Tracking)

OptimalTime O(n)Space O(1)

Expand right one character at a time, incrementing its count and updating max_freq, the highest frequency of any single character seen so far inside the window. If the window size minus max_freq exceeds k — meaning even replacing every non-majority character would not be enough — shrink from left by one. Note that max_freq is never decreased on shrink: it only ever needs to be a valid historical bound to prove a window of that size was once achievable, so this does not affect correctness, only simplifies the code.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        left = 0
        max_freq = 0
        best = 0
        for right, ch in enumerate(s):
            count[ch] = count.get(ch, 0) + 1
            max_freq = max(max_freq, count[ch])
            window_len = right - left + 1
            if window_len - max_freq > k:
                count[s[left]] -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

Tracing s = "AABABBA", k = 1:

leftright
A
0
A
1
B
2
A
3
B
4
B
5
A
6
maxFreq = 1best = 1
1 / 7
comparingseendiscarded

Window [0,0] = A. maxFreq = 1, size 1, 1 - 1 = 0 <= k.

Correctness: the check window_len - max_freq <= k is exactly the condition that the window can be made all one character using at most k replacements — replace every character that is not the most frequent one. Using a historical max_freq never over-counts what is achievable (it is a true frequency that existed), so it never accepts an invalid window; it also never causes us to miss the true best, since the window only ever shrinks by exactly one when it becomes invalid, keeping every valid window length considered.

Complexity: right visits each index once and left moves at most n times total — O(n) time. The count map holds at most 26 uppercase letters — O(1) space.