Longest Repeating Character Replacement: Sliding Window

LeetCode 424, Longest Repeating Character Replacement, asks you to find the length of the longest substring you can create where every character is the same, given that you can replace at most k characters.

For example, given s = "ABABACBA" and k = 2, the answer is 5. The substring "ABABA" can become "AAAAA" by replacing the two B's.

This is one of the best problems for leveling up your sliding window frequency game. If you can solve Longest Substring Without Repeating Characters, this is the natural next step. Instead of tracking a set, you track character frequencies. And instead of checking for duplicates, you use a formula to decide when your window is too big.

Why brute force is too slow

The brute force approach checks every substring, counts each character, and sees if you can make the whole substring uniform with at most k replacements.

def character_replacement_brute(s, k):
    best = 0
    for i in range(len(s)):
        for j in range(i, len(s)):
            substring = s[i:j + 1]
            max_freq = max(substring.count(c) for c in set(substring))
            if len(substring) - max_freq <= k:
                best = max(best, len(substring))
    return best

This is O(n^2 * 26) at best: two nested loops for the substrings, and up to 26 character counts per substring. For n = 100,000, that is way too slow.

The issue is the same as always: you are throwing away your frequency counts every time you slide to a new substring. What if you kept them updated incrementally?

The key insight: window_size - max_freq

Here is the idea that makes this problem click. For any window of characters, think about it this way:

• max_freq is the count of the most frequent character in the window.
• window_size - max_freq is how many characters you need to replace to make the entire window uniform.
• If that number is <= k, the window is valid. You can afford the replacements.
• If it is > k, the window is too big. Shrink from the left.

That is it. The formula window_size - max_freq > k is your shrink condition. Everything else is standard sliding window mechanics.

Walking through it step by step

Let's trace through s = "ABABACBA" with k = 2. We maintain left (orange) and right (green) pointers, a frequency map, and the max_freq value.

The answer is 5, from the window "ABABA" (indices 0 through 4). We can replace both B's with A to get five consecutive A's.

The code

Here is the complete solution in Python:

def character_replacement(s, k):
    freq = {}
    left = 0
    max_freq = 0
    best = 0

    for right in range(len(s)):
        # Expand: add new character to frequency map
        freq[s[right]] = freq.get(s[right], 0) + 1
        max_freq = max(max_freq, freq[s[right]])

        # Shrink: if replacements needed exceed k
        while (right - left + 1) - max_freq > k:
            freq[s[left]] -= 1
            left += 1

        best = max(best, right - left + 1)

    return best

Let's break down each piece:

1. freq is a dictionary mapping each character to its count inside the current window.
2. max_freq tracks the highest frequency of any single character in the window.
3. The for loop expands right one position at a time.
4. After adding the new character, we update max_freq.
5. The while loop checks if window_size - max_freq > k. If so, we remove the leftmost character from the frequency map and advance left.
6. After the window is valid again, we update best.

The max_freq trick explained

This is the part that trips people up. Let's think about why not decrementing max_freq is correct.

Say max_freq is 5 and the window shrinks so the true maximum frequency drops to 4. Does this cause a wrong answer? No, because:

• The window will be slightly smaller than it could be (we shrink a bit too eagerly).
• But we already recorded best when max_freq was 5 and the window was bigger.
• To beat that best, we need a window where max_freq is at least 5 (or higher). So we only care about max_freq going up, not down.

If you prefer, you can decrement properly:

def character_replacement_precise(s, k):
    freq = {}
    left = 0
    best = 0

    for right in range(len(s)):
        freq[s[right]] = freq.get(s[right], 0) + 1

        while (right - left + 1) - max(freq.values()) > k:
            freq[s[left]] -= 1
            left += 1

        best = max(best, right - left + 1)

    return best

This calls max(freq.values()) inside the while loop, which costs O(26) per call. Since the alphabet is fixed at 26, this is still O(n) overall. But the optimized version with the non-decremented max_freq avoids even that small cost.

Complexity analysis

Time: O(n). The right pointer visits each index once. The left pointer also advances at most n times total. Each step does O(1) work (dictionary lookups and updates, one comparison).

Space: O(1). The frequency map holds at most 26 entries (uppercase English letters). This is constant regardless of input size.

Common mistakes

1. Forgetting to decrement frequency when shrinking. When left moves forward, you must subtract 1 from freq[s[left]] before incrementing left. If you skip this, your frequency counts will be wrong and your window will shrink too late (or not enough).

2. Checking frequency of the wrong character. You need the max frequency across all characters in the window, not the frequency of the character you just added. Some people accidentally check only freq[s[right]], which misses cases where a different character is more frequent.

3. Using if instead of while for shrinking. In most cases an if works here because max_freq only goes up by 1 per step, so you only need to shrink by one position. But using while is safer and matches the standard sliding window template. If you use the precise max(freq.values()) version, you may need multiple shrinks.

4. Off-by-one on window size. The window from left to right inclusive has right - left + 1 elements. Forgetting the + 1 will make your formula check (window_size - 1) - max_freq, and you will return answers that are one too large.

The building blocks

This problem decomposes into two reusable pieces that CodeBricks drills independently:

1. Window state tracking

Instead of a set (like in Longest Substring Without Repeating), here you maintain a frequency dictionary. The rhythm is the same: add on expand, remove on shrink. The state always reflects exactly what is inside the current window.

# When expanding (right moves forward):
freq[s[right]] = freq.get(s[right], 0) + 1

# When shrinking (left moves forward):
freq[s[left]] -= 1
left += 1

This same frequency-tracking pattern appears in Minimum Window Substring (tracking needed characters), Permutation in String (tracking character counts), and Find All Anagrams (frequency snapshot matching). The data structure is always a frequency dict, and the add-on-expand, remove-on-shrink rhythm is always the same.

2. Sliding window mechanics

The two-pointer structure where right always moves forward and left moves forward only when the window becomes invalid. Here the validity condition is window_size - max_freq > k. In other problems it might be "sum exceeds target" or "duplicate found." But the expand-and-shrink skeleton stays identical.

left = 0
for right in range(len(s)):
    # update state for s[right]
    while window_is_invalid():
        # remove state for s[left]
        left += 1
    # record best

These two pieces snap together here the same way they do in every sliding window problem. Learning them as isolated building blocks means you can assemble them on the fly for any new problem that uses the same pattern.

Edge cases

Before submitting, verify your solution handles:

• Empty string "": return 0.
• k equals 0: no replacements allowed, so return the length of the longest run of identical characters.
• k greater than or equal to n: you can replace everything, so return len(s).
• All identical "AAAA": return 4 regardless of k.
• All different "ABCD" with k = 2: return 3. You can pick any 3 characters and replace the 2 that differ.

The sliding window solution handles all of these without special cases.

Related posts

• The Sliding Window Pattern - The general pattern guide covering both shrinking and growing window variants
• Longest Substring Without Repeating Characters - The simpler sliding window + set version of this same structure
• Minimum Window Substring - Another frequency-based sliding window that uses the shrink-while-valid variant

Reading through this solution is one thing. Reproducing it from scratch in a week is another. Spaced repetition closes that gap: you revisit the window-state-tracking and sliding-window-mechanics building blocks at increasing intervals, writing the code each time, until the window_size - max_freq formula is something you derive rather than recall.