Sliding Window Frequency Maps

What's being tested

These problems test sliding window reasoning over contiguous arrays/strings with a mutable frequency map that tracks whether the current window satisfies constraints. Interviewers are looking for clean O(n) two-pointer code, correct shrinking logic, and awareness of when a hash map, counter, or fixed-size array is the right state structure.

Patterns & templates

• At-most-k distinct window — expand right, increment freq[x], shrink while len(freq) > k; update answer after restoring validity.

• Bounded flips / replacements — track invalid count, e.g. zeros flipped; shrink while zeros > k; answer is max(ans, right-left+1).

• Frequency map cleanup — when freq[x] == 0, delete x; stale keys make distinct constraints fail silently.

• Longest vs maximum sum window — for length, update after shrink; for sum/count objectives, maintain rolling aggregate alongside freq.

• 2D-to-1D reduction — for matrix variants, fix row/column boundaries, compress into arrays, then apply the same window logic.

• LRU cache contrast — use hash map + doubly linked list for get/put in O(1); do not confuse this with sliding-window frequency state.

Common pitfalls

Pitfall: Shrinking only once with if instead of repeatedly with while leaves the window invalid when multiple removals are required.

Pitfall: Updating the answer before enforcing the constraint can record an impossible window with too many distinct types or flips.

Pitfall: Forgetting to delete zero-count entries causes len(freq) to overcount distinct elements.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.