Why it works
- In a window it is cheapest to keep its most frequent letter and change all the others: that takes the length minus the largest count changes. The window is good when this is at most k.
- A good window stays good when it loses a letter from the left, so for each right it is enough to shrink until the window is good again: what is left is the longest good window ending at right.
- Shrinking may take more than one step: dropping a letter can lower the largest count, and then the window needs as many changes as before.
Complexity
Time O(26 · n): each letter comes in and leaves once, and the largest count is found among at most 26 counts. Memory O(1): at most 26 counts.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗