Find All Anagrams in a String

Given two lowercase strings s and p, return every start index of a substring in s that is an anagram of p.

Return the indices in ascending order.

Input / output

• Input: s: string, p: string
• Output: int[] of start indices

Examples

1. s = "cbaebabacd", p = "abc" returns [0, 6].
2. s = "abab", p = "ab" returns [0, 1, 2].
3. s = "af", p = "be" returns [].

Constraints

• 1 <= p.length <= s.length <= 30000
• s and p contain only lowercase English letters.

Edge cases

• Repeated letters in p matter.
• Overlapping anagrams should all be reported.
• The answer may be empty.

Target complexity

• Aim for O(|s|) time and O(1) extra space beyond the output.

Hints

1. Because only lowercase English letters appear, a 26-length count array is enough.
2. Slide a window of length p.length, adding one new character and removing one old character each step.

Follow-up How would your approach change if s and p could contain arbitrary Unicode characters instead of only lowercase English letters?