Find All Anagrams of a Pattern in a String

Problem Statement

Given a string s and a pattern string p, find all start indices of p's anagrams in s.

An anagram is a permutation of the characters — same character frequencies, different order.

Return the indices in any order.

Constraints

• 1 <= s.length, p.length <= 3 * 10^4
• s and p consist of lowercase English letters only
• Expected: O(n) time, O(1) space (since alphabet is fixed at 26)

Example

Input: s = "cbaebabacd", p = "abc"

Output: [0, 6]

Explanation:

• Index 0: "cba" is an anagram of "abc"
• Index 6: "bac" is an anagram of "abc"

Input: s = "abab", p = "ab"

Output: [0, 1, 2]

What the Interviewer Expects

1. Fixed-size sliding window — window size = p.length. Slide across s.
2. Frequency map comparison — maintain character frequency of the current window. Compare with p's frequency map.
3. Optimized comparison — instead of comparing full maps each time, maintain a matchCount variable. Increment/decrement as characters enter/leave the window.
4. O(n) time — each character is processed exactly twice (enter and leave window).
5. Edge case: p longer than s → return empty array.

Follow-ups

1. What if the alphabet is not limited to 26 characters (e.g., Unicode strings)?
2. What if you need to find anagrams allowing at most K character substitutions?
3. Can you solve this without a frequency map using XOR or hashing? What are the trade-offs?
4. What if p contains wildcards that match any character?