Sliding Window · LC #424
Longest Repeating Character Replacement
Sliding window where validity depends on (window size − max frequency) ≤ k. The non-decreasing maxFreq trick makes this O(n) - the window never shrinks below its historical maximum.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given string `s` and integer `k`, you can change any `k` characters. Return the length of the longest substring containing all the same letter after at most `k` changes.
Sample I/O
Input: s = "ABAB", k = 2 Output: 4 (replace both B's → "AAAA") Input: s = "AABABBA", k = 1 Output: 4
Time: O(n) · Space: O(1)
Intuition
How to Think About It
Intuition
A window is valid if the number of characters we need to replace - those that are NOT the most frequent character - is at most k. That count equals windowSize − maxFreq. Expand right always; shrink left only when the window becomes invalid.
Core Concept
Maintain count[] of character frequencies in the window and maxFreq = highest frequency seen. Validity: (r - l + 1) - maxFreq ≤ k. If invalid, shrink left by 1 (decrement count[s[l]], advance l). The key insight: maxFreq is never decremented - once the window reached a size that required that maxFreq, we never need a smaller answer. Time O(n), Space O(1) (26-char alphabet).
When to use
Sliding window problems where validity is defined by "how many elements need to change to make all elements identical". The pattern generalises to "longest subarray with at most k replacements to satisfy property X".
When NOT to use
When k is very large (≥ n, answer is just n). When the target is not homogeneous replacement (e.g., replace to match a pattern, not a single character).
Key Insights
What to Know Cold
- Window validity condition: (windowSize − maxFreq) ≤ k - characters to change = non-dominant characters.
- maxFreq is intentionally not decremented when shrinking; the window only grows when a larger valid window is possible.
- This means the window size is monotonically non-decreasing - we only slide, never truly shrink.
- The answer is the window size at termination (r - l + 1), since maxFreq tracks the true max over all windows.
- Works for any alphabet - just size the count array to the alphabet size.
1 example
Worked Examples
maxFreq trick - Python
"AABABBA" with k=1 → longest same-char substring after ≤1 replacement.
Track count[], maxFreq; shrink only when (windowSize - maxFreq) > k.
def characterReplacement(s: str, k: int) -> int:
count = {}
l = max_freq = res = 0
for r, c in enumerate(s):
count[c] = count.get(c, 0) + 1
max_freq = max(max_freq, count[c])
if (r - l + 1) - max_freq > k:
count[s[l]] -= 1
l += 1
res = max(res, r - l + 1)
return res
# "AABABBA", k=1 → 4Output: 4
Non-obvious maxFreq-never-decrements trick is a key insight tested at FAANG; shows window can be monotonically non-shrinking.