You are given a string s of uppercase English letters and an integer k. You may choose at most k positions and replace each with any uppercase letter.
Return the length of the longest substring containing a single repeated letter you can obtain after performing at most k replacements.
(length - maxFreq) <= k; slide the left edge when it exceeds k.Input: s = "ABAB", k = 2 Output: 4 Replace the two A's (or two B's) to make "AAAA" or "BBBB" — length 4.
Input: s = "AABABBA", k = 1 Output: 4 Replace one character in "AABA" (or "ABBB") to get a run of 4 identical letters.
- 1 <= s.length <= 10^5 - s consists of only uppercase English letters. - 0 <= k <= s.length
Inside any window, the cheapest way to make every character the same is to keep the most frequent letter and replace all the others. So a window is achievable when the number of "other" characters — its length minus the count of its most frequent letter — is at most k. Grow the window while that holds; slide it when it doesn't.
“Can I replace with any letter?”
Yes — any uppercase letter, so you'd always convert the minority letters into the majority one.
“At most k, or exactly k?”
At most k replacements; using fewer is fine.
“When is a window achievable?”
When (window length − count of its most frequent letter) <= k, i.e. the non-majority letters fit within k replacements.
In a window, I keep the most frequent letter and replace the rest, so the cost is length minus the max letter frequency.
The window is valid when that cost is at most k.
I grow the right edge, tracking the max frequency; if the cost exceeds k, I slide the left edge and keep the best width.
Worked example — s = "AABABBA", k = 1
grow to "AABA" -> maxFreq(A)=3, length 4, cost 4-3=1 <= 1 ok, best 4 extend "AABAB" -> maxFreq=3, length 5, cost 2 > 1 -> slide best stays 4 answer: 4
The minimum replacements to unify a window is length - maxFreq: keep the most frequent letter, convert the rest. The window is valid iff this is at most k.
As the window slides, the recorded maxFreq may be stale (too high), but that only ever lets the window keep or grow its best size — it never produces an answer larger than truly achievable. So you don't recompute it on every shrink.
Because the answer is monotonic, a single left-advance per over-budget step keeps the window from shrinking below the best found — one pass, O(n).
| Check every substring | Sliding window | |
|---|---|---|
| Idea | For each window, cost = length - maxFreq | Grow with maxFreq; slide when cost > k |
| Time | O(n^2) | O(n) |
| Space | O(sigma) | O(sigma) |
The brute recomputes frequencies for every window; the sliding window carries counts forward and slides on cost overflow. Full code is in the Approaches selector below.
Key takeaway
A window is achievable when length - maxFreq <= k (replace all but the most frequent letter). Grow the window tracking maxFreq; when the cost exceeds k, slide the left edge. A stale maxFreq is harmless because the answer is monotonic — one O(n) pass.
count = {}; left = 0; maxFreq = 0; best = 0
for right in 0 .. n-1:
count[s[right]] += 1; maxFreq = max(maxFreq, count[s[right]])
if (right - left + 1) - maxFreq > k: count[s[left]] -= 1; left += 1
best = max(best, right - left + 1)
return best