Longest Repeating Character Replacement
Longest substring achievable with at most k character replacements via a sliding window over character counts.
Problem#
Given a string s and an integer k, return the length of the longest substring you can make all-equal by replacing at most k characters.
Examples#
s = "ABAB", k = 2→4s = "AABABBA", k = 1→4
Constraints#
1 <= s.length <= 10^5, uppercase,0 <= k <= s.length.
Hints#
Hint 1
(window length − max count in window) ≤ k. Slide right; only shrink when violated. Approach#
Sliding window with frequency table. Track maxCount = highest single-character count in the window. The window is valid when length - maxCount ≤ k. When invalid, shift left. We don’t need to recompute maxCount when shrinking because the answer is monotonic in maxCount — keeping a stale max only ever causes us to miss a smaller answer, never a larger one.
Solution#
class Solution {public: int characterReplacement(string s, int k) { int count[26] = {0}; int left = 0, maxCount = 0, best = 0; for (int right = 0; right < (int)s.size(); ++right) { maxCount = max(maxCount, ++count[s[right] - 'A']); if (right - left + 1 - maxCount > k) { --count[s[left] - 'A']; ++left; } best = max(best, right - left + 1); } return best; }};func characterReplacement(s string, k int) int { var count [26]int left, maxCount, best := 0, 0, 0 for right := 0; right < len(s); right++ { count[s[right]-'A']++ if count[s[right]-'A'] > maxCount { maxCount = count[s[right]-'A'] } if right-left+1-maxCount > k { count[s[left]-'A']-- left++ } if right-left+1 > best { best = right - left + 1 } } return best}class Solution: def characterReplacement(self, s: str, k: int) -> int: count = [0] * 26 left = 0 max_count = 0 best = 0 for right in range(len(s)): idx = ord(s[right]) - ord('A') count[idx] += 1 if count[idx] > max_count: max_count = count[idx] if right - left + 1 - max_count > k: count[ord(s[left]) - ord('A')] -= 1 left += 1 best = max(best, right - left + 1) return bestfunction characterReplacement(s, k) { const count = new Array(26).fill(0); const A = 'A'.charCodeAt(0); let left = 0, maxCount = 0, best = 0; for (let right = 0; right < s.length; right++) { const idx = s.charCodeAt(right) - A; count[idx]++; if (count[idx] > maxCount) maxCount = count[idx]; if (right - left + 1 - maxCount > k) { count[s.charCodeAt(left) - A]--; left++; } best = Math.max(best, right - left + 1); } return best;}class Solution { public int characterReplacement(String s, int k) { int[] count = new int[26]; int left = 0, maxCount = 0, best = 0; for (int right = 0; right < s.length(); right++) { int idx = s.charAt(right) - 'A'; count[idx]++; if (count[idx] > maxCount) maxCount = count[idx]; if (right - left + 1 - maxCount > k) { count[s.charAt(left) - 'A']--; left++; } best = Math.max(best, right - left + 1); } return best; }}function characterReplacement(s: string, k: number): number { const count: number[] = new Array(26).fill(0); const A = 'A'.charCodeAt(0); let left = 0, maxCount = 0, best = 0; for (let right = 0; right < s.length; right++) { const idx = s.charCodeAt(right) - A; count[idx]++; if (count[idx] > maxCount) maxCount = count[idx]; if (right - left + 1 - maxCount > k) { count[s.charCodeAt(left) - A]--; left++; } best = Math.max(best, right - left + 1); } return best;}Editorial#
The crucial insight is that maxCount need not be recomputed on shrink — the answer is monotonic. We never grow the window past a length that exceeds maxCount + k; if maxCount is stale-high, we’d accept a window that would be valid for some hypothetical letter, but the recorded length is still bounded by right - left + 1, which is the best we’ve ever seen. The window’s “left” pointer effectively only ever advances by one per outer step.
Complexity#
- Time: O(n).
- Space: O(1) (26 letters).
Concept revision#
Related#