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 the Index of the First Occurrence in a String
Core idea: Slide a window of length
len(needle)acrosshaystackand compare each window to the needle. The twist that sets this apart from the anagram problems in this chapter: order matters. An anagram window asks "do I have the right multiset of characters?"; here we ask "do I have the exact same sequence, character for character, in the same order?" Same sliding frame, stricter question.
Problem, rephrased
You're building the "Find" feature for a text editor (Ctrl+F). The user types a search string, and you must jump the cursor to the first place that exact string appears in the document — or tell them it isn't there.
Concretely: given two strings haystack (the text) and needle (the pattern), return the index in haystack where the first occurrence of needle begins, or -1 if needle never appears. This is LeetCode 28, also known as strStr.
The match must be:
- Contiguous — the characters of
needleappear back-to-back, no gaps. - In order —
"cat"matches"cat", never"tac"or"act". - First — if the pattern appears several times, return the smallest starting index.
haystack |
needle |
Output | Why |
|---|---|---|---|
"sadbutsad" |
"sad" |
0 |
"sad" starts at index 0 (also at 6, but 0 wins) |
"leetcode" |
"leeto" |
-1 |
"leeto" never appears as a contiguous block |
"hello" |
"ll" |
2 |
"ll" begins at index 2 |
"abc" |
"" |
0 |
empty needle matches at the start by convention |
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