127. Find All Anagrams in a String

Medium · String

Given a string `s` and a pattern string `p`, find all starting indices in `s` where an anagram of `p` occurs as a substring.

An anagram is a word or phrase formed by rearranging the letters of another, using each letter at most once. For this problem, we consider any contiguous substring of `s` with the same length as `p` and containing exactly the same character frequencies as `p` to be an anagram.

Return the indices in ascending order.

Examples

Example 1
Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
Explanation: The substring "cba" at index 0 is an anagram of "abc". The substring "bac" at index 6 is also an anagram of "abc".
Example 2
Input: s = "abab", p = "ab"
Output: [0, 1, 2]
Explanation: The substrings "ab" at index 0, "ba" at index 1, and "ab" at index 2 are all anagrams of "ab".

Constraints