Find all anagrams

Given a string and a word, return all starting indices where the word's anagrams occur.

anagrams strings sliding-window frequency-count

Write a function `find_anagram_indices(s: str, p: str) -> list` that takes a string `s` and a string `p`. Return a list of starting indices (0-based) in `s` where a contiguous substring is an anagram of `p`. The order of indices in the result should be increasing. If no anagram is found, return an empty list.

An anagram of `p` is a permutation of the characters in `p`. For example, if `p = "abc"`, then "bca", "cab", and "abc" are anagrams. All strings consist of lowercase English letters only.

Constraints

- 1 <= len(s) <= 10^5
- 1 <= len(p) <= 10^5
- len(p) <= len(s) (if len(p) > len(s), return [])
- Characters are lowercase English letters.
- Your solution should run in O(n) time where n = len(s), using O(1) extra space (constant alphabet).

Example

```python
find_anagram_indices("cbaebabacd", "abc")  # [0, 6]
find_anagram_indices("abab", "ab")          # [0, 1, 2]
find_anagram_indices("hello", "world")      # []
```

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a frequency counter for p and a sliding window of length len(p) over s.

Keep track of how many character counts are currently matching to update efficiently.

When the window slides, update the counts for the character going out and the character coming in.

If the number of matching character counts equals the number of distinct characters in p, record the window start index.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.