Longest Repeating Character Replacement
Find the longest substring that can become all one character after at most k replacements.
Pattern fit
The window stays valid as long as windowLength - maxFrequency <= k, which makes it a textbook window with one dominant frequency statistic.
Key observation
The number of replacements needed equals window size minus the count of the most frequent character inside the window.
Target complexity
O(n) / O(1)
How to break down the solution cleanly
The window stays valid as long as windowLength - maxFrequency <= k, which makes it a textbook window with one dominant frequency statistic.
The number of replacements needed equals window size minus the count of the most frequent character inside the window.
Confirm that the answer can be derived from a moving contiguous interval.
Choose the window state: sum, distinct count, frequency, or matched characters.
Reference implementation
Python# Generic pattern template
# Variable size sliding window
left = 0
window = {}
answer = 0
for right, value in enumerate(nums):
add(window, value)
while not is_valid(window):
remove(window, nums[left])
left += 1
answer = update(answer, left, right, window)
# Fixed size sliding window
window = initialize(nums[:k])
answer = evaluate(window)
for right in range(k, len(nums)):
remove(window, nums[right - k])
add(window, nums[right])
answer = update(answer, right - k + 1, right, window)
Common pitfalls
Trying to recompute the exact max frequency on every shrink unnecessarily.
Confusing the dominant character count with the number of distinct characters.
Common follow-ups
Why can a stale max-frequency value still keep the solution correct?
How is this different from longest substring without repeating?
Continue with related problems
Build repeatable depth inside the Sliding Window cluster before moving on.