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 move: maintain count[] for the window; slide with count[entering] += 1 and count[leaving] -= 1; valid when window counts == target counts (track a match-counter for O(1))](https://maangioassets.blob.core.windows.net/diagrams/coding-interview/101/chapters/sliding-window/rolling-dictionary/rolling-dictionary-summary-diagram-1.svg)
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.
Find All Anagrams in a String
Core idea: Slide a fixed-size window of length
len(p)acrosss, and keep a rolling count map of the characters currently inside it. Each step you add one character on the right and drop one on the left — one in, one out — never re-counting the window from scratch. Whenever the window's counts equalp's counts, you've found an anagram; record its start index.
Problem, rephrased
Imagine you're a security scanner reading a stream of lowercase letters one at a time — say the raw text flowing through a chat filter. You're hunting for a specific bag of letters, p, but the bad guys are allowed to scramble the order. So "abc", "cab", and "bca" are all hits; you don't care about arrangement, only that the exact same letters with the exact same counts appear consecutively. Every time a window of len(p) consecutive characters contains precisely that bag, you flag where it started.
That's an anagram search. An anagram of p is any rearrangement of p's characters — same letters, same multiplicities, different order.
Formally (LeetCode 438): given strings s and p (both lowercase English letters), return all start indices of substrings of s that are anagrams of p. The output order doesn't matter.
s |
p |
Output | Why |
|---|---|---|---|
"cbaebabacd" |
"abc" |
[0, 6] |
s[0:3]="cba" and s[6:9]="bac" are both rearrangements of "abc" |
"abab" |
"ab" |
[0, 1, 2] |
"ab", "ba", "ab" — three overlapping windows all match |
"aaaa" |
"aa" |
[0, 1, 2] |
repeats are fine; every adjacent pair is an anagram |
"abc" |
"abcd" |
[] |
p is longer than s, so no window can exist |
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson