Find All Anagrams in a String
Given two strings s and p, return the start indices of all occurrences of p's anagrams in s.
- 1 <= s.length, p.length <= 3 * 10⁴
- s and p consist of lowercase English letters.
Intuition
Find all anagrams in a string returns every starting index where a substring of s is an anagram of p. Since anagrams have equal length, only windows of length p.length can qualify — which immediately suggests a fixed-size sliding window.
Checking each window by sorting or building a fresh count is O(n × m). The improvement comes from reusing work between adjacent windows:
- Consecutive windows differ by exactly two characters — one leaves the left, one enters the right — so update the counts rather than recomputing them.
So each window costs O(1) to maintain instead of O(m).
Comparing frequency maps at every position still costs O(26) per window, which is acceptable but avoidable. A match counter removes even that: track how many of the 26 letters currently have exactly the right count, and a window is an anagram when that counter reaches 26.
Updating the counter correctly is where care is needed. When a character's count changes, check whether it just became correct or just stopped being correct, comparing against the target before and after the change. Testing only one side leaves the counter permanently wrong.
The simpler comparison version is easier to get right and fast enough for the constraints — worth preferring unless the counter version is written carefully.
The first window must be built before the loop begins, then slid one position at a time. Anagrams need not be contiguous in p, only equal in multiset, which is exactly what the counts capture.
The same fixed-width window as Permutation in String, collecting every match instead of returning on the first. The starting index is r - k + 1, since r is the window's right edge.
Approach
Before reading on: price up what counting everything costs here, then ask what makes a window invalid, and which pointer should move when it is. Aim for O(n) time and O(1) space.
Fix the window size
Anagrams have equal length, so only windows of length p.length can match. The window size never changes, which is what makes the sliding update possible.
Build the target counts
Count each character's frequency in p. A window matches when its own counts equal these exactly — order within the window is irrelevant.
Slide by updating, not recomputing
Adjacent windows differ by two characters. Decrement the outgoing character and increment the incoming one, making each step O(1) instead of O(m).
Compare counts per window
With a 26-letter alphabet, comparing the two count arrays is O(26) — constant. This version is simple and fast enough for the constraints.
Or track a match counter
Count how many letters have exactly the right frequency. Check whether each change just made a letter correct or just broke it — testing only one side leaves the counter permanently wrong.
Record the starting index
When a window matches, append its left index. The problem asks for start positions, not the substrings themselves.
Cost of the scan
Each character enters and leaves the window once, giving O(n) time with the counter, or O(26n) with array comparison. Space is O(1) for the fixed alphabet.
Solution & live demo
Common pitfalls
Recording the right index instead of the left
res.append(r)
res.append(r - k + 1)
The answer is the anagram's starting position. Reporting the right edge shifts every index by k - 1, which looks plausible until compared against expected output.
Rebuilding the counter for each window
for i in range(len(s) - k + 1):
if Counter(s[i:i+k]) == need: res.append(i)have[ch] += 1 ... have[left_ch] -= 1
Slicing and counting per position is O(nk). The sliding window adds one character and removes one, so each step is constant regardless of k.
Not guarding against p being longer than s
need = Counter(p) for r in range(len(s)):
if k > len(s):
return []The window can never reach full width, so r >= k - 1 is never true and the loop runs pointlessly — and any index arithmetic on r - k would be negative. Returning early is both correct and clearer.
Edge cases
No window of that width exists, so the results list stays empty; the loop condition naturally prevents any comparison from firing.
Overlapping windows at consecutive start indices are all recorded since the scan never skips ahead after a match.
The need map's counts greater than 1 are handled the same way as unique characters -- matches is keyed on distinct letters reaching their required count, not on total character count.
matches never reaches the needed key count for any window, and the function returns an empty list.