356. Find All Anagrams in a String
You are given two strings s and p, both made of lowercase English letters. Find every position in s where an anagram of p begins: a substring of s with length |p| that uses exactly the same letters as p, in any order, with the same multiplicities.
Return the 0-based start indices of all such substrings, in increasing order. If p is longer than s, or no window matches, return an empty list.
Example 1:
Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
Explanation: The window "cba" starting at index 0 and the window "bac" starting at index 6 are both rearrangements of "abc".
Example 2:
Input: s = "abab", p = "ab"
Output: [0, 1, 2]
Explanation: "ab" (index 0), "ba" (index 1) and "ab" (index 2) each use one a and one b — windows may overlap.
Constraints:
- 1 ≤ s.length, p.length ≤ 3 * 10⁴
- s and p consist of lowercase English letters.
Hints:
Two strings are anagrams exactly when their 26-entry letter-count arrays are equal. Comparing the count array of every length-|p| window of s against p's count array already avoids sorting.
Consecutive windows differ by just two characters: one enters on the right, one leaves on the left. Update the window's counts in O(1) per slide instead of recounting, and track how many of the 26 letters currently match so the comparison is O(1) too.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "cbaebabacd", p = "abc"
Expected output: [0, 6]