LeetCode 424 ·
Medium
Longest Repeating Character Replacement
Replace at most k characters to make the longest run of one repeated letter.
Try it
Step through the core mechanic. The simulator below runs the sliding window shape this problem is built on.
Interactive · Sliding-window walkthrough LC 3: longest substring without repeating characters
0
a
1
b
2
c
3
a
4
b
5
c
6
b
7
b
start: window is empty
window0 set{} best0
Why sliding window works.
The right edge always moves forward. The left edge only moves forward (never
back). Each character enters and leaves the window at most once, so the total
work is O(n) — even though the algorithm looks like a nested loop.
This "amortised linear" pattern is the core insight: a while-inside-a-for is
fine if the inner work is bounded by total movements, not per-iteration.
The approach
Window is valid when (windowLen − countOfMostFrequentChar) ≤ k. Grow right; when invalid, slide left. The max-frequency need never decrease for the answer to stay correct.
| Aspect | Value |
|---|---|
| Pattern | Sliding window |
| Recognise it by | Longest window valid after ≤k replacements. |
| Time complexity | O(n) |
| Space complexity | O(1) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.