Find All Anagrams in a String

Missing Number

Return every starting index where p appears as an anagram inside s.

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?

- Every candidate substring must have exactly the same length as `p`.
- That makes this a sliding-window problem rather than a variable-size window like minimum cover.

Look for fixed-size windows

- For every start index, build a fresh 26-letter frequency array for the substring and compare it with `p`.
- This is correct, but it repeats almost all of the counting work between neighboring windows.

Recount each window from scratch

- Count `p` once, count the first window once, then update the window in `O(1)` per move.
- Because the alphabet size is fixed at 26, comparing the two count arrays is still constant time.

Slide one fixed-size window across s

- Add the new right character, remove the old left character, and compare the arrays.
- Every window is visited exactly once.

Update counts incrementally

Trace `s = "abab"`, `p = "ab"`.

| window | indices | counts match? | answer |
|---|---|---|---|
| `"ab"` | `[0,1]` | yes | `[0]` |
| slide right -> `"ba"` | `[1,2]` | yes | `[0,1]` |
| slide right -> `"ab"` | `[2,3]` | yes | `[0,1,2]` |

Only one character enters and one leaves on each step, so recomputing the full frequency table is unnecessary.

Dry run / sliding-window trace

A fixed-size sliding window with 26-letter frequency arrays finds every anagram in linear time and constant extra space.