Longest Repeating Character Replacement ​
Longest Repeating Character Replacement — LeetCode
You may replace at most k characters in the string. Find the length of the longest substring of a single repeating character you can produce.
Approach ​
Two methods: One has $O(26n)$ time complexity. Other has $O(n)$.
First one, keep two pointers. Keep the counts of the characters inside the window as we move the right pointer. charactersToReplace = windowSize - counts.Values.Max(). If this is bigger than k, move left pointer and decrease count of the character till the charactersToReplace is <=k.
Second one, same as above, but instead of doing counts.Values.Max(), we keep a maxF that we will update only if some value for some character is higher than any frequency we've seen. Rest of the algorithm is the exact same. This works because we have to maximize the value of both maxF and windowSize to get the longest string.
Remarks ​
I have no idea how the second approach works. I'm just parroting. Neetcode says the second approach is not expected in interviews.
https://youtu.be/gqXU1UyA8pk?si=7WLZ6LB_xa5qAOkB