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.
Permutation in String
Core idea: A permutation of
s1is just a substring ofs2with the exact same letter multiset ass1. So slide a fixed-size window of widthlen(s1)acrosss2, keep a rolling count map that you update in O(1) per step (add the entering char, drop the leaving char), and ask one question at every position: do these counts matchs1's counts? The first time they do, returnTrueand stop.
1. The problem, in a fresh setting
LeetCode 567. Given two lowercase strings s1 and s2, return True if s2 contains any substring that is a permutation of s1 — otherwise False. ("Permutation of s1" = a rearrangement of s1's letters, i.e. an anagram of s1 appearing as a contiguous chunk of s2.)
Reframed: you have a bag of letters (the multiset of s1). You're scanning a long ribbon of text. Is there anywhere on the ribbon a contiguous stretch that uses exactly that bag — same letters, same counts, no more, no less? You only need a yes/no, so the moment you find one window that matches, you're done.
s1 |
s2 |
Output | Why |
|---|---|---|---|
"ab" |
"eidbaooo" |
True |
window "ba" is a permutation of "ab" |
"ab" |
"eidboaoo" |
False |
no length-2 window is {a:1, b:1} |
"abc" |
"bbbca" |
True |
the last window "bca" is a permutation of "abc" |
"adc" |
"dcda" |
True |
window "dca" matches {a:1, c:1, d:1} |
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