Substring Anagrams

Find all start indices where a substring is an anagram of a given pattern.

strings sliding-window hash-map anagram

Write a function `find_anagram_start_indices(s: str, p: str) -> list[int]` that returns a list of all start indices (in increasing order) in `s` where a substring of length `len(p)` is an anagram of `p`. A substring is an anagram of `p` if it contains the exact same characters with the same frequencies, in any order.

For example, `s = "cbaebabacd"` and `p = "abc"` -> indices `[0, 6]` because `"cba"` at index 0 and `"bac"` at index 6 are anagrams of `"abc"`.

Assume `s` and `p` consist of lowercase English letters only. If `len(p) > len(s)`, return an empty list.

Constraints

- 1 <= len(s), len(p) <= 10^5
- The total time must be O(len(s)) or O(len(s) + alphabet_size) (use a sliding window).
- All characters are lowercase English letters ('a' to 'z').

Example

>>> find_anagram_start_indices("cbaebabacd", "abc")
[0, 6]
>>> find_anagram_start_indices("abab", "ab")
[0, 1, 2]
>>> find_anagram_start_indices("aaaa", "aa")
[0, 1, 2]

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a sliding window of fixed size len(p) and keep a character frequency count for the current window.

Compare the window frequency dictionary with the pattern frequency dictionary, or track the number of matching character counts.

When you move the window right, add the new character and remove the old one, updating the match count accordingly.

Only start from index 0 if the first window already matches, then slide until the end.

Test Results

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