Frequency Maps in Windows
Frequency maps let a window reason about duplicates, distinct counts, anagrams, and coverage by updating character or value counts at the endpoints.
Why Counts Matter
Many sliding-window problems are not about numeric sums. They ask whether the current substring has repeated characters, whether it contains all required letters, whether two windows are anagrams, or how many distinct values are present. In those cases, the window state is a set of counts.
Counts preserve information that a boolean set loses. If a character appears three times and one copy leaves, the character is still present. Frequency maps make endpoint updates exact instead of guessing from membership alone.
Array vs HashMap
For lowercase English letters, int[26] is fast, compact, and easy to update with c - 'a'. For ASCII strings, int[128] is common. For arbitrary integers, Unicode characters, or values with a large range, use a HashMap from value to count.
The trade-off is fixed universe versus flexibility. Arrays have excellent constants when the alphabet is known. Hash maps handle broader inputs but require careful zero-count removal when distinct-key size matters.
Need and Match Counters
A full frequency comparison on every window is often too slow. Instead, maintain a small counter that summarizes how close the window is to meeting the target. For anagrams, a missing counter can track how many required characters still need to be matched. For minimum window substring, formed can track how many required character types currently meet their needed counts.
This turns validation into O(1) after each endpoint move. The frequency structure stores detailed counts, while the match counter answers the yes-or-no question quickly.
Shrinking With Counts
When left moves, decrement the count for the leaving element or increment the remaining need, depending on how you model the state. If a count drops to zero in a hash map, remove the key when the number of distinct values matters. If a required count stops being satisfied, update the match counter immediately.
Most bugs in frequency windows come from one-sided updates. If entering a character can make a requirement satisfied, leaving that character can make it unsatisfied. Treat the two endpoint operations as inverse transactions.
Fixed-length frequency window
The array stores remaining needs for the current fixed-length window, while missing is the compact counter that tells whether all required characters are covered.
Key Takeaways
- Use frequency state when the window must reason about duplicates, distinct values, anagrams, or coverage.
- Choose **int[26]**, **int[128]**, or **HashMap** based on the input universe.
- A match or need counter avoids comparing entire frequency structures on every move.
- Endpoint updates must be symmetric: every entering update needs a correct leaving inverse.