You get a string of capital letters, and a number k. You may change at most k characters. Return the longest run of one repeated letter you can make.
DSA Animator › DSA Revision › Strings › Longest Repeating Character Replacement
Remember: changes needed equal window length minus the top count. The window slides, and never shrinks by more than one. The video solves Longest Repeating Character Replacement (LeetCode 424, Medium) with the Sliding Window pattern from the Strings topic, and you can replay every step in the interactive Longest Repeating Character Replacement animation.
You get a string of capital letters, and a number k. You may change at most k characters. Return the longest run of one repeated letter you can make.
A A B A B B A, with k equal to 1. In A A B A, change the B, and you get four A in a row. The answer is 4.
Trying every substring and every letter is very expensive. We want one pass.
In a window, keep the most frequent letter, and change the rest. So the changes needed are the window length minus the max frequency. If that is more than k, the window is invalid. Then drop one character from the left, and slide forward. The max frequency never needs to go down, because the answer only grows when it grows.
Right 0 is A: nothing to change. Right 1 is A: the max frequency is 2. Right 2 is B: one change needed, length 3. Right 3 is A: A appears 3 times, one change, length 4, a new best. Right 4 is B: length 5 needs two changes, more than k. So drop the left A, and the window is back to 4. Right 5 is B: two changes again, so drop another A. Right 6 is A: the same, so drop a B. No valid window grew past 4, so the answer is 4.
In code, keep 26 counts, left, and the max frequency. For each right, count its letter and update the max. If the length minus the max exceeds k, uncount the left letter and move left. Update the best every step. It is O of n time and O of 1 space.
Remember: changes needed equal window length minus the top count. The window slides, and never shrinks by more than one.