Longest Repeating Character Replacement: the window validity trick

The validity condition for this problem fits in one line: (window_size - max_freq) <= k. If the number of characters you'd need to replace to make the window uniform exceeds your budget k, the window is invalid. Everything else — the two pointers, the frequency map, the outer loop — is machinery to maintain that invariant while pushing the window as large as possible.

The subtlety is in what max_freq means and why you can afford to be imprecise about it.

What the problem is actually asking

You have a string of uppercase letters and a budget of k replacements. You want the longest contiguous substring where, after spending at most k replacements, every character is the same.

The optimal strategy inside any window is obvious: keep the most frequent character, replace everything else. So the cost of making a window uniform is window_size - count_of_most_frequent_character. The constraint is that this cost must not exceed k.

That's the entire problem, restated as an inequality: (right - left + 1) - max_freq <= k.

What the constraints force

1 <= s.length <= 10^5 rules out O(n²) immediately and definitely O(n³). You need O(n). The string consists of only uppercase English letters — that caps the frequency map at 26 entries, so space is effectively O(1) regardless of the algorithm. k can be 0 (no replacements allowed) or as large as s.length (replace the entire string), so both extremes need to work without special-casing.

The 26-character alphabet is a quiet gift. Because there are only 26 distinct values, operations on the frequency map cost O(26) = O(1). No hash collision concerns. This also means the brute-force O(n²) — though too slow for 10^5 — beats the naive O(n³) by reusing the map instead of rebuilding it. And it's the same reuse idea that the sliding window takes to its logical conclusion.

Brute force O(n³): enumerate every substring

The clearest starting point checks every (i, j) pair. For each window, build the frequency map from scratch, find the most frequent character, compute the replacement cost, and update the answer if the cost fits within k.

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

public class Solution {
    public int CharacterReplacement(string s, int k) {
        int maxLength = 0;
        int n = s.Length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                var charCount = new Dictionary<char, int>();
                for (int idx = i; idx <= j; idx++) {
                    charCount[s[idx]] = charCount.GetValueOrDefault(s[idx], 0) + 1;
                }
                int maxFreq = charCount.Values.Max();
                if ((j - i + 1) - maxFreq <= k)
                    maxLength = Math.Max(maxLength, j - i + 1);
            }
        }
        return maxLength;
    }
}

O(n³) time, O(1) space (at most 26 entries in the map). This hits time-limit-exceeded at n = 10^5 — a 10^15 operation count is not happening. But it makes the validity check concrete: (j - i + 1) - max_freq <= k is the whole test. Every approach that follows preserves exactly this condition.

Brute force O(n²): incremental frequency map

You can fix i and extend j step by step, updating the count for s[j] instead of rebuilding from scratch. The inner loop body shrinks from O(n) to O(1), bringing the whole thing to O(n²).

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

public class Solution {
    public int CharacterReplacement(string s, int k) {
        int maxLength = 0;
        for (int i = 0; i < s.Length; i++) {
            var charCount = new Dictionary<char, int>();
            for (int j = i; j < s.Length; j++) {
                charCount[s[j]] = charCount.GetValueOrDefault(s[j], 0) + 1;
                int maxFreq = charCount.Values.Max();
                if ((j - i + 1) - maxFreq <= k)
                    maxLength = Math.Max(maxLength, j - i + 1);
            }
        }
        return maxLength;
    }
}

O(n²) time (the Max() call is O(26) = O(1) since the alphabet is fixed), O(1) space. Still too slow at n = 10^5, but it exposes the structural problem to fix next: when i advances, we throw away the entire frequency map and start over. The sliding window fixes that.

Quick walkthrough on s = "ABAB", k = 2:

• i=0, j=0: window "A", cost = 1 - 1 = 0 <= 2. Length 1.
• i=0, j=1: window "AB", max_freq('A')=1, cost = 2 - 1 = 1 <= 2. Length 2.
• i=0, j=2: window "ABA", max_freq('A')=2, cost = 3 - 2 = 1 <= 2. Length 3.
• i=0, j=3: window "ABAB", max_freq('A' or 'B')=2, cost = 4 - 2 = 2 <= 2. Length 4. Answer.

Sliding window: O(n)

Instead of restarting from each i, maintain a single window with two pointers. When right advances, update only the count for s[right]. When the window goes invalid, advance left by one and update only the count for s[left]. The frequency map stays current throughout and is never rebuilt.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        char_count = {}
        left = 0
        max_freq = 0
        max_length = 0
 
        for right in range(len(s)):
            char_count[s[right]] = char_count.get(s[right], 0) + 1
            max_freq = max(max_freq, char_count[s[right]])
 
            if (right - left + 1) - max_freq > k:
                char_count[s[left]] -= 1
                left += 1
 
            max_length = max(max_length, right - left + 1)
 
        return max_length

public class Solution {
    public int CharacterReplacement(string s, int k) {
        var charCount = new Dictionary<char, int>();
        int left = 0, maxFreq = 0, maxLength = 0;
 
        for (int right = 0; right < s.Length; right++) {
            charCount[s[right]] = charCount.GetValueOrDefault(s[right], 0) + 1;
            maxFreq = Math.Max(maxFreq, charCount[s[right]]);
 
            if ((right - left + 1) - maxFreq > k) {
                charCount[s[left]]--;
                left++;
            }
 
            maxLength = Math.Max(maxLength, right - left + 1);
        }
 
        return maxLength;
    }
}

O(n) time, O(1) space. Each character is added once and removed at most once.

By-hand trace on "AABABBA", k = 1

This is the example from the problem statement. Walking through it step by step is the fastest way to see why max_freq doesn't need to be kept perfectly accurate.

The diagram above shows the window at its maximum size (right=3, left=0, size=4). The state table:

right=0  s[r]='A'  count={A:1}        max_freq=1  size=1  cost=0  valid
right=1  s[r]='A'  count={A:2}        max_freq=2  size=2  cost=0  valid
right=2  s[r]='B'  count={A:2,B:1}   max_freq=2  size=3  cost=1  valid
right=3  s[r]='A'  count={A:3,B:1}   max_freq=3  size=4  cost=1  valid
right=4  s[r]='B'  count={A:3,B:2}   max_freq=3  size=5  cost=2  INVALID
         remove s[left=0]='A' -> count={A:2,B:2}, left=1, max_freq stays 3
         window size=4
right=5  s[r]='B'  count={A:2,B:3}   max_freq=3  size=5  cost=2  INVALID
         remove s[left=1]='A' -> count={A:1,B:3}, left=2, max_freq stays 3
         window size=4
right=6  s[r]='A'  count={A:2,B:3}   max_freq=3  size=5  cost=2  INVALID
         remove s[left=2]='B' -> count={A:2,B:2}, left=3, max_freq stays 3
         window size=4

Answer: 4

The window reached size 4 at right=3 and never grew past that. At right=4 it tried to reach size 5 but the validity check failed. From that point on, left shadows right one step behind, keeping the window locked at 4. max_freq stayed at 3 the whole time after right=3, which is correct: we're not interested in whether the current window actually achieves frequency 3 — we're asking whether any future window of size 5 could. Once one did, the bar is set.

The two counterintuitive choices in the optimal solution

Why left moves by exactly one, not until valid. When (right - left + 1) - max_freq > k, you might expect a while loop: keep shrinking until the window is valid again. The code does a single left += 1. This is right because we're hunting for the longest window ever seen. If the window was size L and just went invalid, shrinking to L-1 and advancing right by one keeps it at L. There's no value in looking at anything shorter than L — we've already beaten that. So the window is monotonically non-decreasing in size.

Why max_freq can be stale. After removing s[left], max_freq does not decrease — even if the removed character was the most frequent. This means max_freq might overstate the true maximum in the current window. That's okay: max_freq represents the best frequency ever seen across the window's history. The validity check (right - left + 1) - max_freq > k uses this historical max to decide whether to hold the window size or let it grow. If the current window can't match the historical max_freq, the window stays the same size and waits for a new character to push some frequency higher. The answer at each step — right - left + 1 — is either a valid window or exactly the same size as the best valid window seen, which is what we want.

Complexity comparison

Space is O(1) for all three because the alphabet is fixed at 26 uppercase letters — the frequency map never holds more than 26 entries.

Edge cases

k = 0 — no replacements. The answer is the longest run of a single repeated character in the original string. The sliding window handles this: any window with two or more distinct characters immediately violates (size - max_freq) > 0, so left catches up, and the window only ever holds a uniform run.

k >= s.length — you can replace the entire string. Answer is always s.length. No special case needed: the validity condition is always satisfied and the window grows to fill the string.

Uniform string — s = "AAAA", k = 2. max_freq equals window_size throughout. The validity condition never triggers. Answer is s.length.

Single character — s = "A". The loop runs once, left=0, right=0, max_length=1. Correct.

k larger than necessary — s = "ABCD", k = 10. Every window is valid (replacing 3 of 4 characters costs 3 <= 10). The window grows to the full string and returns 4.

All distinct characters, k = 0 — s = "ABCDE", k = 0. The window can never hold more than one character. Answer is 1. max_freq stays at 1 throughout, and (size - 1) > 0 triggers immediately whenever size > 1.

Where this sits in the sliding window series

This problem is the second in the sliding-window series, right after the fixed-window warmup in Best Time to Buy and Sell Stock. The key new idea here is the variable-size window: the window can grow or hold, and the decision at each step depends on a validity condition you maintain with a frequency map.

The condition here — window_size - max_freq <= k — is one of the cleanest in this problem class. It's worth internalizing because the same shape reappears:

Max Consecutive Ones III (1004) — identical structure, binary array. k flips from 0 to 1. The condition maps directly: (right - left + 1) - count_of_ones <= k. Do this immediately after 424; it takes about five minutes once you have 424 solid.

Permutation in String (567) — fixed-size sliding window over 26-character frequency vectors. The validity check changes (all frequencies must match the target), but the expand-and-slide structure is the same mechanical pattern.

Minimum Window Substring (76) — now you want the shortest window containing all characters of a target. The while-loop instinct is correct there: shrink as far as possible each time you find a valid window. Doing 76 after 424 makes the contrast between longest and shortest window strategies concrete.

Longest Substring Without Repeating Characters (3) — variable-size window where the validity condition is "no duplicate character." Different constraint, same structure.

I'd ship the sliding window for any real system. The O(n²) brute force is a useful check for small inputs during development, but at n = 10^5 it's 10^10 operations and just doesn't finish. The sliding window version is not only asymptotically better — it's the natural extension of the O(n²) idea, just taken one step further: instead of restarting the map at each new i, you carry it forward and subtract the leftmost character when the window needs to contract.