MediumHash TableStringSliding WindowUpdated Sep 2026

438. Find All Anagrams in a String

Asked at Google, Meta, Amazon, Microsoft and 2 more

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Hash Table

Companies

6

Problem

You are given two strings, s and p. An anagram of p is a string made from exactly the same characters as p, each used the same number of times, but possibly in a different order.

Your job is to find every position in s where a substring of length len(p) is an anagram of p. Return a list of the start indices of those substrings. The order of the indices in your answer does not matter.

A substring must be a contiguous block of s — the characters have to sit next to each other. Since every anagram of p has the same length as p, you only ever look at windows of exactly len(p) characters. If s is shorter than p, the answer is an empty list.

Look for windows that match p's letters

scba ✓bac ✓cbaebabacd0123456789Only the windows at index 0 and index 6 contain exactly one a, one b and one c.pabcThe pattern p: any window with these same letter counts is an anagram.
p is "abc", so every window of length 3 in s is checked against the letters a, b and c.

Constraints

  • ●1 <= s.length, p.length <= 3 * 10^4
  • ●s and p consist of lowercase English letters only

Examples

Example 1
Inputs = "cbaebabacd", p = "abc"
Output[0,6]
WhyThe window starting at index 0 is "cba", which uses one a, one b and one c — same as "abc". The window starting at index 6 is "bac", also one of each. No other window of length 3 has exactly these three letters, so only 0 and 6 are recorded.
Example 2
Inputs = "abab", p = "ab"
Output[0,1,2]
WhyEvery window of length 2 here is either "ab" or "ba". Both contain one a and one b, so all three start positions (0, 1 and 2) are valid. Index 3 is not listed because a window of length 2 cannot start there.

Asked At

6 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
UberMediumView all Uber questions →
WalmartMediumView all Walmart questions →

How to Think About It

1

An anagram has the same character frequencies. Use a fixed-size sliding window of length len(p) on s.

2

Build a frequency map of p. Slide across s, maintaining a frequency map of the current window. When frequencies match, it's an anagram.

3

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.

4

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.

Slide a fixed window and compare counts

swindowcbaebabacd0123456789startFirst window "cba" has counts a:1 b:1 c:1, equal to p, so index 0 is added.swindowcbaebabacd0123456789startSlide right: drop 'c', add 'e'. Now the window is "bae" and the counts nolonger match.swindowcbaebabacd0123456789startAfter more slides the window "bac" matches again, so index 6 is added.add s[i], remove s[i - len(p)]if window counts == p counts: record i - len(p) + 1
Keep a count of the current window, move it one step at a time, and record the start index whenever the counts equal p's counts.
ComplexityTime O(n)Space O(1)Each slide updates only two character counts in O(1), and the frequency tables hold at most 26 letters, so the extra memory does not grow with the input.

What Trips People Up in Real Interviews

1

Confusing this with "find all substrings." You're looking for anagrams of p, not all substrings of s.

2

Comparing full frequency maps at each step. Instead, track a counter of matched characters for O(1) comparison.

3

Not handling the case where s is shorter than p. Return an empty list immediately.

4

Forgetting to remove characters from the frequency map when they go to 0. Otherwise, the map comparison fails.

5

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

O(n) time
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 result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.