Algorithm

Find All Anagrams

Sliding Window Pattern

Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order. An anagram is a word or phrase formed by rearranging the letters of a different word using all the original letters exactly once.

CONSTRAINTS
  • 1 <= s.length, p.length <= 3 * 10^4
  • s and p consist of lowercase English letters only
EXAMPLE 1
Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
"cba" at index 0 and "bac" at index 6 are both anagrams of "abc".
EXAMPLE 2
Input: s = "abab", p = "ab"
Output: [0, 1, 2]
Windows "ab"(0), "ba"(1), and "ab"(2) are all anagrams of "ab". They overlap, and all three count.
EXAMPLE 3
Input: s = "aa", p = "bb"
Output: []
No window of s contains a 'b' at all, so no window's letters match p's. The result is empty.
Can the windows overlap?
Yes. In 'abab' with p = 'ab', the anagrams at indices 0, 1, and 2 overlap each other. Every valid start index is reported independently.
What if s is shorter than p?
No anagram of p can fit, so return an empty list.
In what order should indices be returned?
Any order is accepted, but the natural left-to-right scan already produces them in increasing order.
How is comparing the tallies still O(1)?
There are only 26 possible lowercase letters, so comparing two tallies is a fixed 26-slot check — constant time, independent of the string length.

This is the same job as Permutation in String, with one change in the goal. There, we asked "does s contain any rearrangement of p?" and could stop at the first yes. Here we must collect the start index of every window in s that is a rearrangement of p — so instead of returning on the first match, we record its position and keep gliding to the end.

Everything that made permutation-checking work carries over unchanged. Two strings are anagrams exactly when their letter counts match, so we never sort or generate rearrangements — we compare tallies.

Why the brute force is too slow, again

Let m = len(p). The naive plan walks every window of length m and rebuilds its letter count from scratch to compare against p.

python
from collections import Counter
def find_anagrams_naive(s, p):
    n, m = len(s), len(p)
    target = Counter(p)
    res = []
    for i in range(n - m + 1):
        if Counter(s[i:i+m]) == target:   # recounts m letters every window
            res.append(i)
    return res

That is O(N × m) — the exact overlap-wasting we fixed in Maximum Sum Subarray and Permutation in String. Neighbouring windows differ by only one letter out and one letter in, so recounting the whole window each time is throwing the shared middle away.

The rolling tally, collecting every hit

Carry a 26-letter tally of the current window, patch it one-in / one-out as the window slides, and each time the tally equals p's tally, append the window's start index i - m + 1. No early return — we want them all.

python
from collections import Counter
def find_anagrams(s, p):
    n, m = len(s), len(p)
    if m > n: return []
    target = Counter(p)
    window = Counter(s[:m])          # first window, built once
    res = []
    if window == target: res.append(0)
    for i in range(m, n):
        window[s[i]] += 1            # incoming letter
        window[s[i - m]] -= 1        # outgoing letter
        if window[s[i - m]] == 0:
            del window[s[i - m]]     # drop bare zeros so the tallies compare equal
        if window == target:
            res.append(i - m + 1)    # start index of THIS window
    return res
Crucial Notethe recorded index is i - m + 1, the window's left edge — not i, which is its right edge. When the incoming letter sits at i, the window spans i - m + 1 .. i, and the answer wants where the anagram starts.
Worked Example:s = "cbaebabacd", p = "abc"
Target {a:1, b:1, c:1}, width 3.
- Window "cba" (start 0) → {c:1, b:1, a:1}. Match — save 0.
- add e, drop c → "bae" {b:1, a:1, e:1}. No.
- add b, drop b → "aeb" {a:1, e:1, b:1}. No (the 'e' is wrong).
- add a, drop a → "eba" {e:1, b:1, a:1}. No.
- add b, drop e → "bab" {b:2, a:1}. No.
- add a, drop b → "aba" {a:2, b:1}. No.
- add c, drop a → "bac" (start 6) {b:1, a:1, c:1}. Match — save 6.
- Result: [0, 6].

Windows can overlap — in s = "abab", p = "ab" the answer is [0, 1, 2] — which is fine, because the tally never resets; it just keeps sliding one letter at a time.

Same pattern, wider goal

Nothing about the pattern changed from Permutation in String — same fixed width len(p), same 26-letter tally as state, same +1/−1 fold. Only slot (d), what we record, is different: instead of "return true on the first match" it is "append the start index on every match, then carry on." That is the useful lesson — when a problem shifts from "is there one?" to "find all of them", the sliding window itself does not change; you only stop returning early and start collecting. The recognition signals are identical: anagram / permutation wording (so, letter counts), a fixed target length, and a long text to scan.

Interactive Strategy Visualization

Find All Anagrams

p="abc"
O(N) Complexity
a
b
c
c
0
b
1
a
2
e
3
b
4
a
5
b
6
a
7
c
8
d
9
Start Indices Found
0

Frequency Matching

Anagrams are just character frequency matches. Instead of generating permutations, we use a frequency map of 26 characters to check for equality in O(1).

Step-by-Step Logic

Step 1: Initial window 'cba'. All characters {a, b, c} are present. Found index 0!

O(N × M log M) Sort Each Window
→
O(N × M) Recount Each Window
→
O(N) Fixed Sliding Window