Rolling Dictionary

What is this?

Sometimes you don't just care how big the window is — you care exactly which letters are inside it. So as the window slides like a spotlight across a string, you keep a little tally of each character it covers. When a letter slides in you bump its count up; when one slides out you bump it down. Checking whether the window matches some target then becomes a quick glance at the tally instead of re-counting from scratch.

💡 Fun fact: This rolling-count trick is the backbone of fast text search in tools like grep, and a close cousin — the rolling hash — powers plagiarism detectors and Git's own delta compression by fingerprinting sliding chunks of data.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: When a window problem is about which characters are inside (not just a sum), carry a rolling frequency map that you update one-in / one-out as the window slides. Comparing that map to a target tells you, in O(1) with a match-counter, whether the window is an anagram / permutation / exact match — turning repeated re-counting into a single pass.

The move

The subtlety is what you compare: a multiset match (anagram/permutation — order doesn't matter) versus an ordered match (exact substring search — order does matter).

The problems

• Find All Anagrams in a String — fixed window, return every index whose count map equals the pattern's.
• Permutation in String — same engine as an existence check with early exit.
• Find the Index of the First Occurrence — the contrast: ordered matching (use a sliding compare, or rolling-hash / KMP), not a multiset.

Key takeaways

• Carry a count map and update it incrementally — one in, one out per slide.
• A match-counter compares two maps in O(1) (track how many letters are at the target count).
• Multiset vs ordered: anagrams/permutations ignore order; substring search needs exact order.
• Why interviewers love it: it tests whether you maintain derived state incrementally instead of recomputing.

Start here: Find All Anagrams in a String, then Permutation in String.