Earliest Substring That Is a Rearrangement of a Pattern
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a text `s` and a pattern `p`, find the first place in `s` where some rearrangement of `p` appears as a contiguous substring. Return the smallest index `i` such that `s[i : i + len(p)]` contains exactly the same characters as `p`, with the same multiplicities. Return `-1` if no such substring exists.
### Function Signature
```python
def first_anagram_index(s: str, p: str) -> int:
```
### Rules
- A substring qualifies when its length is `len(p)` and every character occurs in it exactly as many times as in `p`. A substring equal to `p` itself qualifies.
- Return the smallest qualifying starting index (0-indexed), or `-1` if there is none, including when `len(p) > len(s)`.
### Constraints
- `1 <= len(s) <= 10^5` and `1 <= len(p) <= 10^5`
- `s` and `p` consist only of lowercase English letters `'a'` to `'z'`.
- The numeric limits and the alphabet are practice assumptions; the original report stated neither.
### Examples
**Example 1**
```text
s = "cbaebabacd", p = "abc"
Output: 0
```
Both `"cba"` (index 0) and `"bac"` (index 6) are rearrangements of `"abc"`; the first one starts at 0.
**Example 2**
```text
s = "eidbaooo", p = "ab"
Output: 3
```
**Example 3**
```text
s = "aaa", p = "aaaa"
Output: -1
```
Overview: Find the starting index of the first substring of a text that is a rearrangement of a given pattern, or report that none exists. Tests fixed-length sliding windows, character-frequency bookkeeping and linear-time scanning of long strings with an early exit.