Problem · LC 424

Longest Repeating Character Replacement

Medium
◧ Intermediate · window with char frequency map→ Expanding

How to recognize it

You can perform at most k character replacements. Find the longest substring with repeating characters after replacements. Signal: "replace", "at most k", "character replacement".

The core idea

Use a sliding window with a frequency map. Track the most frequent character. If (window_size - max_freq) ≤ k, the window is valid (we can replace up to k chars). If > k, shrink the window from left.

Why It's Tricky

Understanding that we need to replace (window_size - max_freq) characters to make the entire window the same char is non-obvious. Also, when shrinking, you must update the frequency map.

The Key Insight

The key is: chars_to_replace = window_size - max_freq_in_window. If this is ≤ k, the window is valid. We DON'T need to update max_freq when shrinking; just shrink the window.

Step-by-Step Walkthrough

Example: "ABAB", k=2

Window [A] → [AB] → [ABA] → [ABAB]
At [ABAB]: size=4, max_freq=2, to_replace=4-2=2 ≤ k=2 ✓
Valid! Max length = 4

"We can replace 2 B's to get AAAA."

time O(n)
space O(1)
longest_repeating_character_replacement
def characterReplacement(s, k):
    freq = {}
    left = 0
    max_freq = 0
    max_length = 0
    for right in range(len(s)):
        freq[s[right]] = freq.get(s[right], 0) + 1
        max_freq = max(max_freq, freq[s[right]])
        while right - left + 1 - max_freq > k:
            freq[s[left]] -= 1
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

Interview gotchas

  • Don't reset max_freq when shrinking — it's the max ever seen in this window expansion.
  • Characters can be any uppercase letter, so use a size-26 array or a hashmap.
  • Window_size - max_freq is the number of chars we need to replace.

💡 What to Say in the Interview

  • Say: "I'll use a sliding window with a frequency map."
  • Key insight: "I need to replace (window_size - max_freq) characters."
  • Condition: "If replacements ≤ k, the window is valid."
  • Complexity: "O(n) time, O(1) space (at most 26 letters)."

↳Variants they'll pivot to

Solve the base problem, then interviewers escalate. These are the usual next steps — knowing the connection is worth more than memorizing each.