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.
Given a text `s` and a pattern `p`, find the first place in `s` where some rearrangement of `p` appears as a contiguous substring.
A substring qualifies when its length is `len(p)` and every character occurs in it exactly as many times as in `p` (same characters, same multiplicities). A substring equal to `p` itself qualifies.
Return the smallest starting index `i` (0-indexed) such that `s[i : i + len(p)]` qualifies, or `-1` if there is none. In particular, return `-1` when `len(p) > len(s)` (for example, `s = "aaa"`, `p = "aaaa"` gives `-1`).
Implement `first_anagram_index(s, p)`, which returns an integer.
### Constraints
- `1 <= len(s) <= 10^5` and `1 <= len(p) <= 10^5`
- `s` and `p` consist only of lowercase English letters `'a'` to `'z'`.
- `len(p)` may exceed `len(s)`.
- The result is `-1` or an index below `10^5`, so it never exceeds `2^31 - 1` and fits in a 32-bit `int` in every language.
The numeric limits and the alphabet are practice assumptions; the original report stated neither.
### 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
```
The windows `"ei"`, `"id"` and `"db"` do not qualify; `"ba"` at index 3 is the first that does.
Constraints
- 1 <= len(s) <= 10^5 and 1 <= len(p) <= 10^5
- s and p consist only of lowercase English letters 'a' to 'z'.
- len(p) may exceed len(s); the answer is then -1.
- The result is -1 or an index below 10^5, so it never exceeds 2^31 - 1 and fits in a 32-bit int.
Examples
Input: ('a', 'a')
Expected Output: 0
Explanation: Minimum sizes: the single letter matches at index 0.
Input: ('a', 'b')
Expected Output: -1
Explanation: Minimum sizes with no match, distinguishing -1 from 0.
Hints
- A qualifying substring always has length exactly len(p); if p is longer than s, there is nothing to check.
- Compare how many times each letter occurs, not just which letters occur: "abb" is not a rearrangement of "aab".
- Examine starting indices from left to right, include the last possible start len(s) - len(p), and stop at the first one that qualifies.