424. Longest Repeating Character Replacement
Asked at Microsoft, Goldman Sachs, DE Shaw
Difficulty
Medium
Time
O(n)
Space
O(1)
Pattern
Hash Table
Companies
3
Problem
You get a string s made of uppercase English letters, and an integer k. You may pick at most k characters in the string and change each one into any other uppercase letter.
Return the length of the longest substring you can turn into a block of one repeated letter using those changes. A substring means a run of characters that sit next to each other — you cannot skip characters.
For any window of characters, the cheapest way to make it uniform is to keep the letter that appears most often and rewrite all the others. So the number of changes a window needs is window_length - count_of_most_common_letter. A window is usable when that number is <= k.
How many changes does a window need?
Constraints
- ●
1 <= s.length <= 10^5 - ●
s consists of only uppercase English letters - ●
0 <= k <= s.length
Examples
s = "ABAB", k = 24s = "AABABBA", k = 14Asked At
3 companies| Company | Difficulty | |
|---|---|---|
| Microsoft | Medium | View all Microsoft questions → |
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
| DE Shaw | Medium | View all DE Shaw 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.
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).
Sliding window that never shrinks below the best
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
O(n) timedef 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Longest Repeating Character Replacement?
Longest Repeating Character Replacement is asked at Microsoft, Goldman Sachs, DE Shaw. 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.