Problem
Given a string of uppercase letters and an integer k, find the length of the longest substring you could turn into all-one-character by changing at most k characters within it.
Signal
A variable window bounded by a "budget" — "longest substring where at most k
characters can be wrong" — is sliding window plus a frequency count, with a
validity check shaped like window_size - most_frequent_count <= k.
Approach
Expand the window right, keeping a frequency count of the characters inside it. A window is valid if replacing every character except its most frequent one costs at most k replacements. Whenever it's invalid, shrink from the left by one and adjust the count. Track the longest valid window seen.
Skeleton
count = {}
left = 0
max_freq = 0
best = 0
for right, c in enumerate(s):
count[c] += 1
max_freq = max(max_freq, count[c])
while (right - left + 1) - max_freq > k:
count[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
Solution
def character_replacement(s: str, k: int) -> int:
count: dict[str, int] = {}
left = 0
max_freq = 0
best = 0
for right, c in enumerate(s):
count[c] = count.get(c, 0) + 1
max_freq = max(max_freq, count[c])
while (right - left + 1) - max_freq > k:
count[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return best
Complexity
O(n) time — left and right each advance at most n times, and count updates are O(1) over a fixed 26-letter alphabet. O(1) space — a fixed-size count table.
Pitfalls
- Not "fixing"
max_freqafter a shrink looks like a bug on first read, but it's a correct shortcut: a stale, too-highmax_freqcan only ever delay recognizing that the window could grow again — it never lets the window shrink below a length that was genuinely achievable, so recomputing the true max on every shrink is wasted work. - Confusing "at most k replacements" with "exactly k" — a window using fewer than k is still valid.
- Off-by-one on the validity check: it's
window_length - max_freq, compared with> k(strictly), not>= k.