Medium · Window with Dominant Frequency
Understand → Visualise → Practice.
Replace at most k characters and return the longest substring that can be made one repeated character.
In a window, the letters you must replace are window length − count of its most frequent letter. Grow the window, and shrink it from the left when that exceeds k.
Add text[right] to the counts and update the highest count seen.
While (window length − highest count) > k, remove text[left] and move left.
The answer is the largest valid window length.
O(n) time and O(alphabet) space.
The highest count need not be decreased when shrinking; a stale value never makes the answer too large.
Read the full guide first: Strings: Frequencies, Matching and Palindromes.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.