Longest Repeating Character Replacement
Medium Variable window + max frequency
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
You may change at most k characters of an uppercase string. Return the longest substring that can be made of one repeated letter.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: change at most k letters to get the longest run of one letter.
Why this works: a window is fine when (length - count of its most common letter) ≤ k, because those other letters are the ones you change.
Example: "AABABBA", k = 1
"AABA": length 4, most common A=3 → 1 change ✓"AABAB": 5 - 3 = 2 > 1 → slide leftbest 4
✦Hints open one at a time
↗Approach
Expand right, update counts and the highest count seen. If the window needs more than k changes, move left by one (the window slides instead of shrinking). The final window size is the answer.
</>Solution (Java)
class Solution {
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int left = 0, maxFreq = 0, best = 0;
for (int r = 0; r < s.length(); r++) {
maxFreq = Math.max(maxFreq, ++count[s.charAt(r) - 'A']);
if (r - left + 1 - maxFreq > k) { // too many letters to change
count[s.charAt(left) - 'A']--;
left++;
}
best = Math.max(best, r - left + 1);
}
return best;
}
}!Common mistake
Recomputing the true max frequency every time you shrink — correct but unnecessary; the stale maximum still gives the right answer.
- Time: O(n).
- Space: O(26).