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