438. Find All Anagrams in a String

438

MediumSliding WindowHash map of character countsFixed-size window frequency match

Find All Anagrams in a String

Given strings s and p, return the starting indices of every substring of s that is an anagram of p (same multiset of characters), in any order.

Open official problem prompt ↗

In plain English

Find every position where a fixed-width slice of s is a rearrangement of p.

Picture it like this

Slide a stencil of width len(p) along a strip of letters. At each stop you check whether the letters showing through match your target bag of letters, regardless of their order.

Example

Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
Why: The substring starting at index 0 is "cba" and at index 6 is "bac", both anagrams of "abc".

Constraints

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

Pattern lesson

See the pattern, then code

Fixed-size window frequency match

↗

Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. An anagram check only cares about character frequencies, not order. Slide a window of width len(p) across s, updating counts in O(1) per step, and record positions where the window counts equal p's counts.

New words, made simpleKnow these before the algorithm

Anagram: A string with exactly the same character counts as another.
Frequency map: A count of how many times each character appears.
Fixed-size window: A window whose width never changes; the left edge advances in lockstep with the right.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Sort every substring

Redundant re-sorting of overlapping windows is far too slow.

For each start index, sort the length-p substring and compare to sorted p.

Time O(n * m log m)Space O(m)

Fresh Counter per window

Wastes the overlap between consecutive windows.

Recount all len(p) characters at each position.

Time O(n * m)Space O(1)

Best choiceIncremental count window

Only constant work per step; 26-letter maps make equality checks constant.

Add the entering character and remove the leaving one, comparing maps in O(26).

Time O(n)Space O(1)

The rule we keep true

Invariant

After processing index i (for i >= k-1) the window map holds exactly the counts of the substring s[i-k+1 .. i], so a map equality means that substring is an anagram of p.

Why this is correct

Reasoning

Equal character multisets is the exact definition of an anagram. Because the window keeps precise counts and deletes zero entries, dict equality with need is true if and only if the current width-k substring is an anagram of p.

The algorithm in three movesSay these aloud before coding

1Build the frequency map of p and an empty window map

p counts = {a:1, b:1, c:1}

2Add each new character on the right

window at [0..2] 'cba' -> {c:1,b:1,a:1} == p -> record 0

3Once the window exceeds len(p), remove the character falling off the left (delete zero entries)

window at [6..8] 'bac' -> match -> record 6

4Whenever the window map equals p's map, record the window's start index

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readch='a'

2 · AskDoes the window match?

3 · Update statewindow={c:1,b:1,a:1}

4 · ResultEquals need -> record start 0.

Key takeaway

The first width-3 window 'cba' matches the target counts of 'abc'.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5-6Length guard
If p is longer than s no anagram can fit, return empty.
2
Lines 12-13Grow on the right
Count the entering character.
3
Lines 14-18Shrink on the left
Once the window is wider than k, drop the outgoing character and delete zero entries so map equality stays exact.
4
Lines 19-20Record matches
When counts equal p's, the window start index i-k+1 is an answer.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

p longer than s -> empty list
p and s identical length with one possible match
repeated characters in p such as p='aab'
no anagram present anywhere -> empty list

Common beginner mistakes

Forgetting to delete keys that hit zero, so Counter equality fails even when the multiset matches
Off-by-one on the recorded start index (should be i-k+1)
Only starting to remove the left character at i >= k instead of the correct window-full condition
Rebuilding the whole window each step and losing the O(n) advantage

Check your understanding

Why must you delete a character key when its count reaches zero rather than leaving it at 0?

PyPython 3 · solution.py

Optimal

1from collections import Counter23class Solution:4    def findAnagrams(self, s: str, p: str) -> list[int]:5        if len(p) > len(s):6            return []7        need = Counter(p)8        window: Counter[str] = Counter()9        k = len(p)10        res: list[int] = []11        for i, ch in enumerate(s):12            window[ch] += 113            if i >= k:14                left = s[i - k]15                window[left] -= 116                if window[left] == 0:17                    del window[left]18            if window == need:19                res.append(i - k + 1)20        return res

Time complexityO(n)Optimized

Space complexityO(1)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMetaMicrosoft

Find All Anagrams in a String

Find All Anagrams in a String

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Sliding Window