Longest Repeating Character Replacement
Asked at Microsoft
Problem
Given a string s of uppercase English letters and an integer k, find the length of the longest substring where you can replace at most k characters to make all characters the same. The trick is maintaining the count of the most frequent character in the window.
Asked At
| Company | Difficulty | |
|---|---|---|
| Microsoft | Medium | View all Microsoft questions → |
How to Think About It
Key insight: in a valid window, the number of characters that need replacement is window_size - max_frequency. If this value is <= k, the window is valid. You can replace the non-dominant characters to match the most frequent one.
Sliding window: maintain a window [left, right]. Expand right. Track character frequencies in the window. Calculate max_freq = count of the most frequent character. If window_size - max_freq > k, shrink from left.
Critical optimization: max_freq never needs to decrease. Even when you shrink the window and a character count decreases, the previous max_freq was valid for a larger window. A smaller window with the same max_freq is still valid. This avoids recomputing max_freq.
Visual walkthrough: s = "AABABBA", k = 1.
- right=0: window="A", counts={A:1}, max_freq=1, size=1, replacements=0. Valid.
- right=1: window="AA", counts={A:2}, max_freq=2, size=2, replacements=0. Valid. max=2.
- right=2: window="AAB", counts={A:2,B:1}, max_freq=2, size=3, replacements=1. Valid. max=3.
- right=3: window="AABA", counts={A:3,B:1}, max_freq=3, size=4, replacements=1. Valid. max=4.
- right=4: window="AABAB", counts={A:3,B:2}, max_freq=3, size=5, replacements=2. Invalid (> k). Shrink left.
- left=1: window="ABAB", counts={A:2,B:2}, max_freq=3 (kept!), size=4, replacements=1. Valid. max=4.
- right=5: window="ABABB", counts={A:2,B:3}, max_freq=3, size=5, replacements=2. Invalid. Shrink.
- left=2: window="BABB", counts={A:1,B:3}, max_freq=3, size=4, replacements=1. Valid. max=4.
- right=6: window="BABBA", counts={A:2,B:3}, max_freq=3, size=5, replacements=2. Invalid. Shrink.
- left=3: window="ABBA", counts={A:2,B:2}, max_freq=3, size=4, replacements=1. Valid. max=4.
Result: 4.
Time: O(n) since each character is visited once by right and at most once by left. Space: O(26) = O(1) for the fixed alphabet size.
Optimal Approach
Sliding window with two pointers (left, right) and a hash map of character frequencies.
- Expand right through the string. Increment count of s[right].
- Track
max_freq= max frequency of any character in the current window. - If
window_size - max_freq > k, the window is invalid. Decrement count of s[left] and increment left. - Update max result = max(result, right - left + 1).
The key insight: max_freq never decreases. Even when a character leaves the window, keeping the old max_freq is safe because it was valid for a larger window.
Walkthrough: s = "ABAB", k = 2.
- right=0: A, counts={A:1}, max_freq=1, size=1. Valid.
- right=1: B, counts={A:1,B:1}, max_freq=1, size=2, reps=1. Valid.
- right=2: A, counts={A:2,B:1}, max_freq=2, size=3, reps=1. Valid.
- right=3: B, counts={A:2,B:2}, max_freq=2, size=4, reps=2. Valid.
Result: 4 (replace both B's to A or vice versa).
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Recomputing max_freq from scratch every time. This makes it O(26n) which is technically O(n) but wasteful. The trick is that max_freq only increases, never decreases. Just track it as you go.
Forgetting that the problem says uppercase English letters only. The alphabet size is constant (26), so O(26) operations are O(1). Don't use a hash map when a 26-element array is simpler.
Confusing "replace at most k characters" with "replace exactly k characters". You can replace FEWER than k. The window is valid if replacements needed <= k, not == k.
Shrinking the window by more than one step at a time. You only need to decrement the count of s[left] and move left by 1. The while loop handles multiple shrinks if needed.
Not handling the edge case where k >= string length. If k >= len(s), you can replace all characters to match any one, so the answer is len(s). Your sliding window handles this naturally, but mention it.
Solution Code
def characterReplacement(s, k):
count = {}
max_freq = 0
left = 0
result = 0
for right in range(len(s)):
count[s[right]] = count.get(s[right], 0) + 1
max_freq = max(max_freq, count[s[right]])
while (right - left + 1) - max_freq > k:
count[s[left]] -= 1
left += 1
result = max(result, right - left + 1)
return resultFrequently Asked Questions
What is the Longest Repeating Character Replacement problem?
Given a string s of uppercase English letters and an integer k, find the length of the longest substring where you can replace at most k characters to make all characters the same. The trick is maintaining the count of the most frequent character in the window.
How do you solve Longest Repeating Character Replacement?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Repeating Character Replacement?
Longest Repeating Character Replacement is asked at Microsoft. It is a medium difficulty problem.
What are common mistakes on Longest Repeating Character Replacement?
- Recomputing `max_freq` from scratch every time. This makes it `O(26n)` which is technically `O(n)` but wasteful. The trick is that `max_freq` only increases, never decreases. Just track it as you go.
- Forgetting that the problem says uppercase English letters only. The alphabet size is constant (26), so `O(26)` operations are `O(1)`. Don't use a `hash map` when a 26-element array is simpler.
- Confusing "replace at most k characters" with "replace exactly k characters". You can replace FEWER than k. The window is valid if replacements needed <= k, not == k.
- Shrinking the window by more than one step at a time. You only need to decrement the count of `s[left]` and move left by 1. The while loop handles multiple shrinks if needed.
- Not handling the edge case where k >= string length. If k >= len(s), you can replace all characters to match any one, so the answer is len(s). Your sliding window handles this naturally, but mention it.