Earliest Substring That Is a Rearrangement of a Pattern

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

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

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

s = "eidbaooo", p = "ab"
Output: 3

Example 3

s = "aaa", p = "aaaa"
Output: -1