Find All Anagrams in a String
Find every start index of an anagram of p in s with a fixed-size sliding window that keeps letter counts up to date as it moves.
Problem Understanding
Find All Anagrams in a String: given strings s and p, return every start index in s where a substring is an anagram of p (the same letters with the same counts, in any order).
Example: s = "cbaebabacd", p = "abc" returns [0, 6]: "cba" and "bac".
The Intuition: A Window That Keeps Its Counts
Every candidate is a substring of length |p|, so use a fixed-size sliding window. Two strings are anagrams exactly when their letter counts match, the same test as Valid Anagram.
Recounting each window would be wasteful. Instead, keep the window's counts current:
- The letter entering on the right:
+1. - The letter leaving on the left:
−1. - If the counts equal
p's, record the start index.
Permutation in String uses the same window but only asks whether one match exists.
Interactive Walkthrough
The window slides across s, with its newest letter filled. It turns green whenever its counts match p, and that start index is recorded. Try Repeats to see why counts matter, not just which letters appear.
Dry Run Table
Input: s = "cbaebabacd", p = "abc"
| Window | Start | Matches p? |
|---|---|---|
| cba | 0 | ✓ |
| bae | 1 | ✗ |
| aeb | 2 | ✗ |
| eba | 3 | ✗ |
| bab | 4 | ✗ |
| aba | 5 | ✗ |
| bac | 6 | ✓ |
| acd | 7 | ✗ |
Answer: [0, 6].
The Solution Template
Two 26-slot count arrays and a window of fixed length.
Find All Anagrams in a String Code
1var findAnagrams = function(s, p) {2 const m = p.length, need = new Array(26).fill(0), have = new Array(26).fill(0), ans = [];3 for (const c of p) need[c.charCodeAt(0) - 97]++;4 for (let i = 0; i < s.length; i++) {5 have[s.charCodeAt(i) - 97]++;6 if (i >= m) have[s.charCodeAt(i - m) - 97]--;7 if (have.every((v, k) => v === need[k])) ans.push(i - m + 1);8 }9 return ans;10};
Edge Cases & Common Mistakes
- p longer than s: no window ever reaches length |p|; the answer is
[]. - Overlapping matches:
s = "abab",p = "ab"gives[0, 1, 2]; keep sliding after a match. - Comparing letter sets instead of counts:
"aab"and"abb"share letters but are not anagrams. - Off-by-one on the left edge: the letter that leaves is
s[i - |p|], and the window starts ati - |p| + 1. - Faster comparison: track how many of the 26 letters currently match, so each move updates a counter instead of comparing arrays.
Summary
Count p once, then slide a window of length |p| over s, adding the entering letter and removing the leaving one. Whenever the two count arrays are equal, record the window's start. O(n) time and O(1) space for a 26-letter alphabet.
More practice: DSA interview questions with answers · patterns cheat sheet