Find All Anagrams in a String
Problem Statement
Given two strings s and p, return all start indices of substrings in s that are anagrams of p. The answer may be returned in any order.
Input
Two lowercase strings: s, the search string, and p, the anagram pattern.
Output
A list of integers containing every start index where the length-p.length window in s has the same character counts as p.
Constraints
- •
1 <= s.length, p.length <= 3 * 10^4 - •
s and p consist of lowercase English letters
Examples
Example 1
s = cbaebabacd, p = abc
[0,6]Example 2
s = abab, p = ab
[0,1,2]Example 3
s = baa, p = aa
[1]Learning Objectives
- Reuse the fixed-window frequency equality pattern to find every match, not just one.
- Convert a successful window position into the correct start index.
- Maintain a match counter safely while adding and removing characters.
- Understand why the window size must remain exactly **p.length**.
Intuition
This is the same Pattern Identification signal as permutation matching: an anagram of p must be contiguous in s and must have fixed length p.length. The only difference is the output. Instead of stopping at the first matching window, collect every start index whose frequency array equals the target frequency array.
The sliding window is powerful because every neighboring candidate shares almost all characters with the previous one. Once the first window is counted, each move changes exactly two counts. That lets us scan s once while preserving a precise anagram test.
Common mistakes
- ×Returning after the first anagram even though the problem asks for all starting indices.
- ×Recording **right - patternLength** instead of **right - patternLength + 1** after a slide.
- ×Letting the window grow beyond **p.length** and comparing counts of different-sized substrings.
- ×Treating anagrams as unique-letter matches and missing repeated characters in **p**.
Algorithm Explanation
Window setup
Use targetCount for p and windowCount for the current fixed-size window in s. Maintain matches, the number of lowercase letters whose target and window counts are equal. Whenever matches == 26, append the window start index to the answer.
Window visualization
For s = cbaebabacd and p = abc, the target counts are a:1, b:1, c:1. The first window cba already matches, so record 0. Sliding to bae loses c and gains e, so the counts no longer match. The same update continues until the window bac at indices 6..8, where a, b, and c all return to count 1. Record 6.
Algorithm
- Create an empty result list.
- If p.length > s.length, return the empty list.
- Build the target counts from p and the first window counts from s.
- Compute the initial matches value across all 26 characters.
- Record index 0 if the initial window matches.
- Slide one position at a time by adding s[right] and removing s[right - p.length], updating matches around both count changes.
- After each slide, if matches == 26, append right - p.length + 1.
Solutions
Solution: Fixed window frequency matching
Every candidate anagram has the same length as p, so the window never needs to expand or shrink conditionally. We slide a fixed-size window and use the same match-counter frequency comparison as Permutation in String, appending each successful start index.
Step-by-step
- Prepare an empty list for answers and return it immediately if p is longer than s.
- Count characters in p and in the first window of s.
- Count how many of the 26 slots are equal.
- Add 0 when the first window matches.
- For every later right index, update the entering character, then the leaving character, preserving a fixed window length.
- Whenever all 26 slots match, add the current start index to the result.
O(n + 26)
O(1)
Each character enters and leaves the fixed window at most once; the result list is output space.
Java implementation
Dry Run
Sample input
s = cbaebabacd, p = abc. The target counts are a:1, b:1, c:1, and the fixed window size is 3.
| right after slide | window bounds | window | important window counts | matches | result |
|---|---|---|---|---|---|
| initial | 0..2 | cba | a:1, b:1, c:1 | 26 | [0] |
| 3 | 1..3 | bae | a:1, b:1, e:1 | 24 | [0] |
| 4 | 2..4 | aeb | a:1, b:1, e:1 | 24 | [0] |
| 5 | 3..5 | eba | a:1, b:1, e:1 | 24 | [0] |
| 6 | 4..6 | bab | a:1, b:2 | 24 | [0] |
| 7 | 5..7 | aba | a:2, b:1 | 24 | [0] |
| 8 | 6..8 | bac | a:1, b:1, c:1 | 26 | [0,6] |
| 9 | 7..9 | acd | a:1, c:1, d:1 | 24 | [0,6] |
Only windows cba and bac make all 26 frequency slots match the target, so the answer is [0,6].
Interview Tips
Make the connection to Permutation in String explicit. The core check is identical; the interview difference is collecting starts accurately. State the formula for the current start after sliding as right - p.length + 1, because off-by-one errors are common here.
Likely follow-ups
- How would you count the number of anagram windows without storing their indices?
- How would the solution change for a large alphabet where 26 arrays are not enough?
- Can you reuse the same helper for both this problem and Permutation in String?
- How would you stream **s** one character at a time and emit matching starts online?
Similar Problems
Key Takeaways
- All anagram windows have fixed length equal to the pattern length.
- Frequency equality is the correct anagram test, especially when duplicates exist.
- A match counter turns repeated array comparison into constant-time slide updates.
- After processing right, the current start is **right - p.length + 1**.