Longest Repeating Character Replacement

1. Initialize Variables

• Create a count object to track the frequency of each character in the current window.
• Set left pointer to 0, maxFreq to 0 (tracks the highest frequency of any single character in the window), and maxLen to 0.

2. Expand the Window

• Iterate right from 0 to s.length - 1.
• Add s[right] to the frequency map and update maxFreq if this character now has the highest frequency.

3. Check the Window Validity

• The number of characters that need to be replaced is windowSize - maxFreq, i.e., (right - left + 1) - maxFreq.
• If this exceeds k, the window is invalid — we need more than k replacements to make all characters the same.

4. Shrink the Window

• While the window is invalid, decrement the count of s[left] and move left forward.
• This shrinks the window until the number of replacements needed is at most k.

5. Update the Maximum Length

• After ensuring the window is valid, update maxLen with the current window size right - left + 1.

6. Return the Result

• After processing all characters, return maxLen — the length of the longest valid substring.

Key Insight

The key observation is that we don't need to track *which* character to replace — we just need to know the most frequent character in the window. The remaining characters (windowSize - maxFreq) are the ones we'd replace. If that count exceeds k, we shrink the window. Notably, maxFreq doesn't need to be perfectly accurate when shrinking — it only needs to be accurate when it leads to a new maximum window, which it always is.