Longest Repeating Character Replacement

How it works

We want the longest window where we can make all characters the same using at most k replacements. Using the true current maximum frequency, the window is valid as long as:

window size – count of the most frequent character ≤ k

Why? Because the characters that aren't the most frequent are the ones we would need to replace.

So while expanding the window, we track:

• the frequency of each character,
• the highest frequency we have seen in the window as it grows (maxf).

After we shrink from the left, maxf may be stale because we do not decrease it. That can temporarily make the current window look valid even when its true current maximum frequency is smaller. This is still correct because such a stale value never increases the answer beyond a window length that was already achievable when maxf was accurate.

If the window is too large under this tracked maxf, we shrink it from the left. This gives us one clean sliding window pass.

Steps

1. Create a frequency map count and initialize l = 0, maxf = 0, and res = 0.
2. Move the right pointer r across the string:
   • Update the frequency of s[r].
   • Update maxf with the highest frequency seen so far.
3. If the tracked condition is violated (window size - maxf > k):
   • Shrink the window from the left and adjust counts.
4. Update the result with the current window size.
5. Return res at the end.

Complexity

• Time complexity: O(n)
• Space complexity: O(m)

Where n is the length of the string and m is the total number of unique characters in the string.

Things to watch for

Not Updating maxf Correctly

The variable maxf tracks the highest frequency seen while expanding the window, not necessarily the exact maximum frequency after every shrink. A common mistake is recalculating the maximum by iterating through all counts after moving the left pointer. In the optimal solution, you do not need to decrease maxf when shrinking. A stale, higher maxf can temporarily make the validity check more permissive and allow an actually invalid current window, but it does not affect correctness because it cannot make the algorithm record a length larger than one that was achievable when maxf was accurate.

Shrinking the Window Too Aggressively

When the tracked condition is violated (window size - maxf > k), you only need to shrink until that condition passes again. A common error is resetting the left pointer too far or not updating character counts properly when moving the left pointer. Make sure to decrement the count of s[l] before incrementing l.

Confusing Window Size Calculation

The window size is r - l + 1, not r - l. This off-by-one error is frequent and leads to incorrect validity checks. For example, if l = 0 and r = 2, the window contains 3 characters, not 2. Always double-check your window size formula in the condition (r - l + 1) - maxf <= k.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        res = 0

        l = 0
        maxf = 0
        for r in range(len(s)):
            count[s[r]] = 1 + count.get(s[r], 0)
            maxf = max(maxf, count[s[r]])

            while (r - l + 1) - maxf > k:
                count[s[l]] -= 1
                l += 1
            res = max(res, r - l + 1)

        return res

class Solution {
public:
    int characterReplacement(std::string s, int k) {
        unordered_map<char, int> count;
        int res = 0;

        int l = 0, maxf = 0;
        for (int r = 0; r < s.size(); r++) {
            count[s[r]]++;
            maxf = max(maxf, count[s[r]]);

            while ((r - l + 1) - maxf > k) {
                count[s[l]]--;
                l++;
            }
            res = max(res, r - l + 1);
        }

        return res;
    }
};