ASAPUtils
The signal
“Longest … such that” again, so it’s a variable window. What makes this one a step up from Longest Substring Without Repeating is that validity is no longer a membership test — it’s arithmetic, and deriving that formula is the actual problem.
Approach ladder
1. Brute force — O(n² · 26)
For every substring and every target letter, count how many changes are needed. Correct, far too slow.
2. Derive the validity condition
Take any window. To make it uniform you keep one letter and change the rest. Which letter do you keep? Obviously the one that already appears most — that minimises the work. So:
replacementsNeeded = windowLength − maxFreq
and the window is valid when windowLength − maxFreq <= k.
That single line is the whole problem. Note it also means you never have to try each of the 26
letters separately: tracking one maxFreq covers them all.
3. Optimal — O(n)
int characterReplacement(string s, int k) {
vector<int> count(26, 0);
int l = 0, maxFreq = 0, best = 0;
for (int r = 0; r < (int)s.size(); r++) {
maxFreq = max(maxFreq, ++count[s[r] - 'A']);
while (r - l + 1 - maxFreq > k) { count[s[l] - 'A']--; l++; }
best = max(best, r - l + 1);
}
return best;
}
function characterReplacement(s, k) {
const count = new Map();
let l = 0, maxFreq = 0, best = 0;
for (let r = 0; r < s.length; r++) {
count.set(s[r], (count.get(s[r]) ?? 0) + 1);
maxFreq = Math.max(maxFreq, count.get(s[r]));
while (r - l + 1 - maxFreq > k) {
count.set(s[l], count.get(s[l]) - 1);
l++;
}
best = Math.max(best, r - l + 1);
}
return best;
}
The maxFreq question everyone asks
When the window shrinks, maxFreq might no longer be accurate — it’s never recomputed. Is that a
bug?
No, and the reason is worth understanding. A stale maxFreq is too large, which makes the
validity test too permissive, which lets the window stay wider than it strictly should. But best
only ever increases, and to record a length of L you must have had a genuinely valid window of
length L at some earlier point with that same maxFreq. So an over-large maxFreq can never
cause you to record a length you didn’t actually achieve.
Recomputing it (an O(26) scan) is also correct and easier to defend under pressure. Both are accepted; know which you wrote and why.
Walkthrough
s = "AABABBA", k = 1:
| r | window | length | maxFreq | replacements | action |
|---|---|---|---|---|---|
| 0 | A | 1 | 1 | 0 | valid, best = 1 |
| 1 | AA | 2 | 2 | 0 | valid, best = 2 |
| 2 | AAB | 3 | 2 | 1 | valid, best = 3 |
| 3 | AABA | 4 | 3 | 1 | valid, best = 4 |
| 4 | AABAB | 5 | 3 | 2 | invalid → shrink |
Complexity
- Time O(n) — both pointers move right only.
- Space O(1) — 26 counters.
Traps
- Recomputing the answer as
maxFreq + k. That can exceed the string length. The answer is the window length. - Shrinking with
ifinstead ofwhile. Usually works here because the window shrinks by at most one per step — but don’t rely on that; usewhile. - Forgetting the input is uppercase.
- 'A', not- 'a'.
Blank re-solve prompt
Given a string and k allowed replacements, return the longest substring you can make uniform. Derive the validity condition before writing any code.