Find All Anagrams in a String

Given a string s and a string p, return all starting indices of p's anagrams in s. Strings contain only lowercase English letters.

Use a sliding window of size len(p) with character counts.

Why this is worth learning

Returning every location changes the output cost: the counting state is constant-size, but the result can contain linearly many indices.

Before coding: one-minute experiment

For s="aaaa" and p="aa", what starts are returned?

Function signature

func FindAnagrams(s string, p string) []int

Inputs / outputs

• s: search string.
• p: pattern string.
• Return: slice of starting indices where an anagram of p begins.

Example

s = "cbaebabacd", p = "abc"
Output: [0,6]

Anagrams at "cba" and "bac".

Constraints

• 0 <= len(s), len(p) <= 100_000
• Strings contain only lowercase letters.

Core idea (near-solution)

An anagram has the same 26-letter counts. Slide a fixed window over s and compare counts with p.

Invariant: the window length is len(p) and the counts reflect exactly the window.

Algorithm (step-by-step)

1. If len(p) > len(s), return empty slice.
2. Build count arrays for p and the first window of s.
3. If counts match, record index 0.
4. Slide the window:
   • Add new right character.
   • Remove old left character.
   • If counts match, record the new left index.
5. Return the list of indices.

Correctness sketch

For every candidate start, maintain the difference between the pattern counts and that window's counts. All differences being zero is equivalent to equal multisets. Updating the leaving and entering letters preserves the vector without rescanning the substring. A match counter can track how many of the 26 coordinates are zero, provided each update accounts for both the old and new zero status. Report exactly those starts with all 26 matches. Each start is visited once, so indices are ordered and none are duplicated. For an empty pattern, every boundary from 0 through len(s) is an empty anagram.

Trace (hand walkthrough)

Example input:
s = "cbaebabacd", p = "abc"
Output: [0,6]

Anagrams at "cba" and "bac".

Walk:
- window "cba" at 0 matches -> add 0
- slide: "bae" (1), "aeb" (2), "eba" (3), "bab" (4), "aba" (5) no match
- window "bac" at 6 matches -> add 6

Pitfalls to avoid

• Returning indices for windows of the wrong size.
• Forgetting the empty-pattern convention: the reference returns every boundary index 0 through len(s), including the end boundary.

Debugging lens

Check the transition through zero when a count changes, including an entering byte equal to the leaving byte. Empty-pattern behavior is explicit rather than borrowed from a different version of this problem.

Complexity

Time: O(len(s)+len(p)) with 26 fixed counts. Auxiliary counting space: O(1). Output space: O(z) for z indices; z can be len(s)+1 for an empty pattern.

Implementation notes (Go)

• Maintain a frequency diff array and a match count.
• Slide the window and record indices when all counts match.

Contract precision

The supplied reference returns indices in ascending order. An empty pattern returns every boundary [0,1,...,len(s)], including [0] for empty text.

Reconstruction checkpoint

For s="aaaa" and p="aa", what starts are returned?

Return to Sliding Window · Module quiz