Find All Anagrams in a String
Asked at Google, Meta, Amazon, Microsoft, Uber, Walmart
Problem
Given two strings s and p, find all the start indices of p's anagrams in s. The answer can be returned in any order.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Uber | Medium | View all Uber questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
An anagram has the same character frequencies. Use a fixed-size sliding window of length len(p) on s.
Build a frequency map of p. Slide across s, maintaining a frequency map of the current window. When frequencies match, it's an anagram.
Optimization: instead of comparing full frequency maps each time, track a "matches" counter. Increment when a character's count in the window equals its count in p. Decrement when it goes out of sync.
Visual walkthrough for s="cbaebabacd", p="abc":
Window size=3. p_count={a:1,b:1,c:1}
Window "cba": c_count={c:1,b:1,a:1} = p_count → match at index 0
Slide: remove c, add e → "bae": no match
Slide: remove b, add b → "aeb": no match
Slide: remove a, add a → "eba": no match
Slide: remove e, add b → "bab": no match
Slide: remove b, add a → "aba": no match
Slide: remove a, add c → "bac": match at index 6
Result: [0, 6]
Edge cases: s shorter than p (return []), p has duplicate characters, all characters same.
Optimal Approach
Step 1: If len(s) < len(p), return [].
Step 2: Build frequency maps for p and the first window of s.
Step 3: Slide the window across s:
Add the new character (right side).
Remove the old character (left side).
If the frequency maps match, record the start index.
Step 4: Return the list of start indices.
Time: O(n) where n = len(s). Each slide is O(1) frequency update. Space: O(1) — at most 26 characters per map.
What Trips People Up in Real Interviews
Confusing this with "find all substrings." You're looking for anagrams of p, not all substrings of s.
Comparing full frequency maps at each step. Instead, track a counter of matched characters for O(1) comparison.
Not handling the case where s is shorter than p. Return an empty list immediately.
Forgetting to remove characters from the frequency map when they go to 0. Otherwise, the map comparison fails.
Using a variable-size sliding window. The window must be fixed at len(p) — you're looking for exact-length anagram matches, not variable-length substrings.
Solution Code
from collections import Counter
def findAnagrams(s, p):
if len(s) < len(p):
return []
p_count = Counter(p)
s_count = Counter(s[:len(p)])
result = []
if s_count == p_count:
result.append(0)
for i in range(len(p), len(s)):
s_count[s[i]] += 1
old = s[i - len(p)]
s_count[old] -= 1
if s_count[old] == 0:
del s_count[old]
if s_count == p_count:
result.append(i - len(p) + 1)
return resultFrequently Asked Questions
What is the Find All Anagrams in a String problem?
Given two strings s and p, find all the start indices of p's anagrams in s. The answer can be returned in any order.
How do you solve Find All Anagrams in a String?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Find All Anagrams in a String?
Find All Anagrams in a String is asked at Google, Meta, Amazon, Microsoft, Uber, Walmart. It is a medium difficulty problem.
What are common mistakes on Find All Anagrams in a String?
- Confusing this with "find all substrings." You're looking for anagrams of p, not all substrings of s.
- Comparing full frequency maps at each step. Instead, track a counter of matched characters for `O(1)` comparison.
- Not handling the case where s is shorter than p. Return an empty list immediately.
- Forgetting to remove characters from the frequency map when they go to 0. Otherwise, the map comparison fails.
- Using a variable-size sliding window. The window must be fixed at len(p) — you're looking for exact-length anagram matches, not variable-length substrings.