Longest Repeating Character Replacement
Problem
You are given a string s of uppercase English letters and an integer k. You may change any character into any other uppercase letter, at most k times in total.
Return the length of the longest substring containing a single repeated letter that you can get after these changes.
Example 1
- Input
s = "ABAB", k = 2- Output
4- Why
- Change both A's to B (or both B's to A).
Example 2
- Input
s = "AABABBA", k = 1- Output
4- Why
- Change the middle A to B to get "BBBB".
Constraints
- 1 ≤ s.length ≤ 10⁵
- 0 ≤ k ≤ s.length
Explanation
A window can be made uniform if window length - count of its most common letter ≤ k: keep the most common letter and change the rest.
Grow the window on the right; when it needs more than k changes, slide the left edge by one. The best window size only ever grows, so the most-common count does not need to be recomputed when the window shrinks.
Approach 1 · Naive
Every start, count as you grow
- Time O(n²)
- Space O(1)
For each start, extend the end while tracking letter counts and the highest count. A window is valid while length - maxCount <= k.
- For each
i, reset 26 counts andmaxCount. - For each
j ≥ i, adds[j], updatemaxCount, and if(j - i + 1) - maxCount <= k, update the best.
class Solution {
public int characterReplacement(String s, int k) {
int best = 0;
for (int i = 0; i < s.length(); i++) {
int[] count = new int[26];
int maxCount = 0;
for (int j = i; j < s.length(); j++) {
maxCount = Math.max(maxCount, ++count[s.charAt(j) - 'A']);
if (j - i + 1 - maxCount <= k) {
best = Math.max(best, j - i + 1);
}
}
}
return best;
}
}class Solution:
def characterReplacement(self, s: str, k: int) -> int:
best = 0
for i in range(len(s)):
count = [0] * 26
max_count = 0
for j in range(i, len(s)):
count[ord(s[j]) - ord('A')] += 1
max_count = max(max_count, count[ord(s[j]) - ord('A')])
if j - i + 1 - max_count <= k:
best = max(best, j - i + 1)
return bestApproach 2 · Optimal
Sliding window
- Time O(n)
- Space O(1)
Expand right each step. If the window needs more than k replacements, move left once (dropping its letter). The window length never shrinks, so at the end it equals the best answer.
- Keep 26 counts,
maxCountandleft = 0. - For each
right: adds[right], updatemaxCount. - If
(right - left + 1) - maxCount > k, removes[left]from the counts and incrementleft. - Return
n - left, the final window length.
class Solution {
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int maxCount = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
maxCount = Math.max(maxCount, ++count[s.charAt(right) - 'A']);
if (right - left + 1 - maxCount > k) {
count[s.charAt(left) - 'A']--;
left++;
}
}
return s.length() - left;
}
}class Solution:
def characterReplacement(self, s: str, k: int) -> int:
count = [0] * 26
max_count = left = 0
for right, c in enumerate(s):
count[ord(c) - ord('A')] += 1
max_count = max(max_count, count[ord(c) - ord('A')])
if right - left + 1 - max_count > k:
count[ord(s[left]) - ord('A')] -= 1
left += 1
return len(s) - leftComplexity compared
| Approach | Time | Space |
|---|---|---|
| Naive Every start, count as you grow | O(n²) | O(1) |
| Optimal Sliding window | O(n) | O(1) |
Key takeaways
maxCountmay be stale after shrinking, and that is fine: only a largermaxCountcan produce a larger answer.- Sliding by one instead of shrinking with a
whilekeeps the window at the best size found so far.
Your notes
Saved in this browser as you type.
Solved it on your own?
Mark it done to track your progress, or star it to come back before an interview.