How to Explain Longest Repeating Character Replacement in a Coding Interview (Step-by-Step)

Longest Repeating Character Replacement is the quintessential variable-size sliding window problem. The trick isn’t the window mechanics — it’s the validity formula. Once you can explain why window_size − max_freq ≤ k determines validity, the rest is straightforward.

In this post, you’ll learn exactly how to walk an interviewer through this problem: the core formula, how the window expands and contracts, a full step-by-step trace, and the subtle gotcha about not decreasing max_freq.

Problem Statement

Examples

Constraints

• 1 <= s.length <= 10⁵
• s consists of only uppercase English letters
• 0 <= k <= s.length

What Is the Problem?

“I need to find the longest contiguous substring where, after replacing at most k characters, all characters in the window are the same. The replacement strategy is always to change minority characters into the most frequent one.”

Step 1: Start With the Brute Force (Then Dismiss It)

The Key Insight

The Validity Formula — The Heart of This Problem

Spend time on this formula in the interview. Draw it out if needed:

“In a window of size 5 with the most frequent character appearing 3 times, I need to replace the other 2 characters. That’s 5 − 3 = 2 replacements. If k ≥ 2, this window is valid.”

Step 2: Explain the Algorithm in Plain English

“I use a sliding window with left and right pointers. I expand the window by moving right forward one character at a time, updating a frequency map and tracking the max frequency in the window. If the window becomes invalid — meaning replacements needed exceed k — I shrink it by moving left forward. At every step I track the maximum valid window size seen.”

Step 3: Talk Through the Code

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count    = {}   # Frequency map of chars in current window
        max_freq = 0    # Max frequency of any single char in window
        left     = 0
        result   = 0

        for right in range(len(s)):
            count[s[right]] = count.get(s[right], 0) + 1     # Expand window
            max_freq = max(max_freq, count[s[right]])          # Update max freq

            # Check if window is valid: replacements needed <= k
            window_size = right - left + 1
            if window_size - max_freq > k:
                count[s[left]] -= 1   # Shrink window from left
                left += 1

            result = max(result, right - left + 1)  # Update best valid window

        return result

There’s a subtle but important optimisation here worth calling out explicitly:

“Notice we never decrease max_freq when the window shrinks. This is intentional — we only care about finding a window larger than the best we’ve seen. If max_freq can’t grow, the window just slides forward at the same size rather than shrinking. This keeps the time complexity O(n).”

Visual Walkthrough

Tracing s = "AABABBA", k = 1:

Full step trace for "AABABBA", k = 1:

Final answer: 4

Step 4: Highlight Edge Cases

Step 5: State Time and Space Complexity

Interview Checklist for Longest Repeating Character Replacement

• Restate — “longest window where replacements needed ≤ k”
• Mention brute force O(n²) and dismiss it
• State the key insight — replacements = window_size − max_freq
• Explain the validity formula clearly — derive it, don’t just state it
• Explain sliding window mechanics — expand right, shrink left when invalid
• Call out the max_freq gotcha — we never decrease it, and explain why
• Handle k=0 and k≥n edge cases
• State O(n) time and O(1) space — fixed 26-char alphabet
• Ask before coding, don’t just dive in

Related Problems to Practice

If you can solve Longest Repeating Character Replacement cleanly, try these next: