Longest Repeating Character Replacement — Sliding Window with K Replacements

Problem Statement#

Given a string s and an integer k, you can replace at most k characters with any other letter. Return the length of the longest substring containing a single repeating character after at most k replacements.

Constraints:

• 1 <= s.length <= 10^5
• s consists of uppercase English letters
• 0 <= k <= s.length

Input:  s = "ABAB", k = 2
Output: 4

Input:  s = "AABABBA", k = 1
Output: 4

Why This Problem Matters#

LeetCode 424 is one of the most-asked sliding window interview problems at Google, Microsoft, Amazon, and Meta. It tests whether you can derive a non-obvious invariant from the problem (window length minus max frequency) instead of brute-forcing every substring. Recruiters use it to separate candidates who memorize templates from those who actually understand the two pointer technique.

The keywords this problem teaches map directly to dozens of follow-ups: "longest substring with at most k...", "max consecutive ones III", "fruit into baskets". Interviewers love it because it has a neat O(n) solution but rewards mathematical reasoning over coding speed.

If you only learn three sliding window problems before a FAANG loop, this should be one of them. It is the canonical "shrinkable window with a constraint" template.

The Core Insight#

The window [l, r] is valid when windowLength - maxFreq <= k, where maxFreq is the count of the most frequent character inside the window. That difference is exactly the number of replacements you would need to make every character match the dominant one.

You do not need to recompute maxFreq when you shrink the window. Even if the true max frequency drops, the answer can never improve unless maxFreq increases — so keeping a stale upper bound on maxFreq is safe and lets you do a one-pass O(n) sweep.

This invariant is the trick. Many candidates write code that recalculates maxFreq after every shrink in O(26), which still works but obscures why the algorithm is correct.

Visual Dry Run#

Trace s = "AABABBA", k = 1.

Answer stays 4 because we never grow the window beyond size 4 with a valid replacement count.

Solution (Optimal)#

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = [0] * 26
        left = 0
        max_freq = 0
        best = 0
 
        for right, ch in enumerate(s):
            count[ord(ch) - ord('A')] += 1
            max_freq = max(max_freq, count[ord(ch) - ord('A')])
 
            # window length - most common char count > k => shrink
            if (right - left + 1) - max_freq > k:
                count[ord(s[left]) - ord('A')] -= 1
                left += 1
 
            best = max(best, right - left + 1)
 
        return best

var characterReplacement = function (s, k) {
    const count = new Array(26).fill(0);
    let left = 0;
    let maxFreq = 0;
    let best = 0;
 
    for (let right = 0; right < s.length; right++) {
        const idx = s.charCodeAt(right) - 65;
        count[idx]++;
        maxFreq = Math.max(maxFreq, count[idx]);
 
        if ((right - left + 1) - maxFreq > k) {
            count[s.charCodeAt(left) - 65]--;
            left++;
        }
 
        best = Math.max(best, right - left + 1);
    }
 
    return best;
};

Time: O(n) — every index is visited at most twice (once by right, once by left). Space: O(1) — fixed 26-slot frequency array.

Common Mistakes#

• Recomputing maxFreq from the entire frequency array on every shrink. Correct, but unnecessary and slows you down in interviews.
• Using if to shrink while increasing the window length on the same iteration. Many candidates accidentally use a while loop and lose the linear bound's elegance.
• Forgetting that maxFreq is allowed to be a stale upper bound — and trying to "fix" it.
• Treating the input as case-insensitive when it is uppercase only. Read constraints.
• Off-by-one errors in window length: it is right - left + 1, not right - left.

Interview Tips#

• Start by stating the invariant: windowLength - maxFreq <= k.
• Justify why a stale maxFreq is safe before writing code — interviewers love this.
• Mention the alternative O(26 * n) version where maxFreq is recomputed; explain why both work but the stale version is cleaner.
• Walk through "AABABBA", k = 1 on the whiteboard before coding.
• After coding, mention follow-ups like "what if the alphabet is unbounded" — answer: use a HashMap and recompute maxFreq lazily.

Follow-up Questions#

• What if the alphabet is unicode? Hint: switch the array to a HashMap.
• What if k can be negative? Hint: clamp to zero or return zero immediately.
• Can you return the actual substring, not just its length? Hint: track bestLeft whenever you update best.
• What if you must use exactly k replacements? Hint: you would need to ensure at least k non-dominant chars exist in the window.
• How does this generalize to "longest substring with at most k distinct chars"? Hint: same template, different invariant.

Key Takeaways#

• LeetCode 424 is solved with a sliding window plus a frequency array of size 26.
• The valid-window invariant is windowLength - maxFreq <= k.
• maxFreq can be stored as a stale upper bound; the answer never improves unless it grows.
• Use if (not while) to shrink the window so the loop stays O(n).
• This template generalizes to "Max Consecutive Ones III", "Fruit Into Baskets", and "Longest Substring with K Distinct".
• Time O(n), space O(1) when the alphabet is fixed.
• The problem appears in Google, Microsoft, and Amazon interviews multiple times per year.