Find All Starting Indices of Anagrams in a String
Implement findAnagramStartIndices
Given two lowercase strings
s and p, return every starting index in s where a contiguous substring is an anagram (a permutation, rearranged) of p.
This is the "find all" version of checking for a single permutation: instead of stopping at the first match, every window of s must be checked. A window is a match precisely when its 26-letter frequency count equals p's. Rebuilding that count for every window works, but the sliding windowSliding WindowMaintaining a running result over a contiguous range that grows or shrinks one element at a time, instead of recomputing the result for every range from scratch. technique keeps the count updated in O(1) per slide — bump the letter entering, drop the letter leaving — instead of recounting all of p.length letters every time.
Example 1:
Input: s = "aabb", p = "ab"
Output: [1]
Example 2:
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Example 3:
Input: s = "abab", p = "ab"
Output: [0,1,2]
+ 8 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ s.length, p.length ≤ 3 × 10⁴ - ●
s and p consist of lowercase English letters only
s =
aabb
p =
ab