Longest Repeating Character Replacement
You may replace at most k characters in an uppercase string. Find the longest substring that can become one repeated character.
Work through the cases
3 examplesInput notation
The string on line 1 and a nonnegative integer k on line 2.Expected result
The maximum length.Case 1
Input
ABAB 2
Expected output
4
Case 2
Input
ABCDE 1
Expected output
2
Case 3
Input
AAAA 0
Expected output
4
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
A window can be made uniform with at most k changes iff its length minus the majority count is at most k. Trying every pair of ends is O(n^2). Expand the right end while tracking the maximum frequency mx. When r-l+1-mx>k, shift the left end by one. The longest legal window has length n-l. There is no need to decrease mx on a left move: we only want the maximum length, and an overestimate of mx only makes the test stricter.
We use a hash table cnt to count the occurrence of each character in the string, and two pointers l and r to maintain a sliding window, such that the size of the window minus the count of the most frequent character does not exceed k.
We iterate through the string, updating the right boundary r of the window each time, updating the count of characters within the window, and updating the maximum count mx of the characters that have appeared. When the size of the window minus mx is greater than k, we need to shrink the left boundary l of the window, updating the count of characters within the window, until the size of the window minus mx is no longer greater than k.
Finally, the answer is n - l, where n is the length of the string.
The time complexity is O(n), and the space complexity is O(|\Sigma|). Where n is the length of the string, and |\Sigma| is the size of the character set. In this problem, the character set is uppercase English letters, so |\Sigma| = 26.
class Solution {
public int characterReplacement(String s, int k) {
int[] cnt = new int[26];
int l = 0, mx = 0;
int n = s.length();
for (int r = 0; r < n; ++r) {
mx = Math.max(mx, ++cnt[s.charAt(r) - 'A']);
if (r - l + 1 - mx > k) {
--cnt[s.charAt(l++) - 'A'];
}
}
return n - l;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.