Coding interview problems › Sliding Window
🪟 Sliding Window Medium
Longest Repeating Character Replacement
Longest Repeating Character Replacement explained: a window is valid while its length minus the top letter count is at most k. O(n) window, tested Python.
Also searched as: character replacement sliding window · longest substring with same letters after k replacements
Try it live Free
Sliding Window
Watch the window slide by adding the element that enters and removing the one that leaves. Here what you track inside the window is a letter count, and the window is valid while length minus top count is at most k.
The problem
Given an uppercase string s and an integer k, you may change at most k characters to any other letter. Return the length of the longest substring that can be made of one repeated letter.
Change both As or both Bs.
"AABA" becomes "AAAA".
The key insight
A window can be turned into one letter if the characters that are not its most frequent letter number at most k, that is window_length - max_count <= k. Grow the window on the right; when it becomes invalid, slide the left edge forward by one so the window never shrinks below the best length found.
Step-by-step approach
- Keep letter counts for the window,
left = 0, andmax_count, the highest count seen in a window. - For each
right, increment the count ofs[right]and updatemax_count. - If
(right - left + 1) - max_count > k, decrement the count ofs[left]and moveleftforward one step. - Track the best window length
right - left + 1. - Return the best length.
Python solution
def character_replacement(s, k):
count = {}
left = max_count = best = 0
for right, ch in enumerate(s):
count[ch] = count.get(ch, 0) + 1
max_count = max(max_count, count[ch])
if (right - left + 1) - max_count > k: # too many to replace
count[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return bestComplexity
Each character enters and leaves the window at most once. The count map holds at most 26 letters.
Common mistakes
- Recomputing
max(count.values())on every step and believing it must be exact; the trick is that a stale, too-highmax_countnever produces a wrong answer, it only stops the window from growing. - Shrinking with a
whileloop and recomputing the max each time, which is correct but slower and easy to get wrong. - Forgetting that the replaced letters must all become the same letter, the window's most common one.
Frequently asked questions
What is the time and space complexity of Longest Repeating Character Replacement?
O(n) time and O(1) space, since the counts cover at most 26 uppercase letters.
Why is it fine that max_count is never decreased?
The answer only improves when a window has a larger max_count than any before. A stale max_count can keep an invalid window the same size, but the recorded best length was achieved by a real valid window earlier.
What if the string has any characters, not just uppercase?
Use a dictionary for counts instead of a 26-slot array. The logic is unchanged and space becomes O(k) for k distinct characters.
Preparing for placements?
Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.
All coding interview problems More Sliding Window Sliding Window lab Placement prep guides
Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.