mediumSliding WindowPure DSA~25 min
Find All Anagram Start Indices
Scanning a long text for every place a short pattern appears in any letter order — the building block of fuzzy substring search.
Problem
Given two strings s and p, return all start indices of substrings in s that are anagrams of p. The output order does not matter.
Input
Two lowercase strings s and p.
Output
A list of start indices where an anagram of p begins.
Constraints
- 1 <= s.length, p.length <= 3 * 10^4
- s and p contain only lowercase English letters.
Examples
Example 1
Input
s = "cbaebabacd", p = "abc"
Output
[0,6]
"cba" at index 0 and "bac" at index 6 are anagrams of "abc".
Example 2
Input
s = "abab", p = "ab"
Output
[0,1,2]
Every length-2 window is an anagram of "ab".