Sliding Window + Frequency Map
Track counts in the window and shrink when fixing the window would cost too many replacements.
0 of 3 problems solved
Sliding Window + Frequency Map
Track counts in the window and shrink when fixing the window would cost too many replacements.
- •Can I track character frequencies inside the window?
- •Is the window valid when replacements needed are at most k?
- •Do I shrink only when the window becomes too expensive to fix?
Here the window is allowed to be a little messy. You can replace up to k characters, so the window stays valid as long as the number of 'wrong' characters is not too large. The useful trick is to track the most frequent character inside the window. If the window size minus that max frequency is greater than k, the window is too expensive to fix, so you shrink it. In plain English: if the room has too many oddballs, tidy it up from the left.
A window is valid when the characters you would need to replace are at most k.
- 1Slide a window over the string with left and right pointers.
- 2Track character frequencies inside the window.
- 3Keep the count of the most frequent character seen in the current window logic.
- 4If window size minus max frequency becomes greater than k, shrink from the left.
- 5Track the largest valid window length.
Trying to recompute the perfect most frequent value from scratch every time makes the solution heavier than it needs to be.
Max Consecutive Ones
Single-pass counter: increment on 1, reset to 0 on 0, track the running maximum.
Sliding Window Maximum
Monotonic deque of indices with decreasing values. Pop the back when a larger element arrives, pop the front when its index falls outside the window.