Find the Earliest Anagram Window
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Find the Earliest Anagram Window
### Problem
Implement `firstAnagramStart(text, pattern) -> index`.
Return the zero-based start index of the earliest contiguous substring of `text` that contains exactly the same character multiset as `pattern`. Character order may differ, but multiplicity must match. Return `-1` if no such substring exists.
### Portable Contract
- `1 <= text.length <= 90,000` and `1 <= pattern.length <= 90,000`.
- Both strings contain only printable ASCII characters from U+0020 through U+007E.
- Characters compare exactly and case-sensitively; `A` and `a` are different.
- If `pattern.length > text.length`, return `-1`.
- Do not modify either input or materialize all candidate substrings.
- Let `B` be the compact UTF-8 JSON byte length of `[text,pattern]`: no whitespace outside strings, and quotation marks and reverse solidus characters use their shortest required JSON escapes. Inputs satisfy `B <= 96,000`.
- The result is `-1` or an index below `90,000`, so its compact JSON encoding uses at most `5` bytes. Serialized input plus result is therefore at most `96,005` bytes.
- Target `O(text.length + pattern.length)` time and `O(1)` auxiliary space for the fixed 95-character alphabet.
The four language signatures use only strings and an integer result:
- Python: `def firstAnagramStart(text: str, pattern: str) -> int`
- JavaScript: `function firstAnagramStart(text, pattern)` returns an integer `Number`.
- Java: `int firstAnagramStart(String text, String pattern)`
- C++: `int firstAnagramStart(const string& text, const string& pattern)`
```hint Fix the candidate length
Every matching substring must contain exactly as many characters as the pattern, so all candidates use one window size.
```
```hint Update only what crosses the boundary
When the window advances one position, one character leaves and one enters; the rest of the frequency state is unchanged.
```
### Examples
```text
text = "cbaebabacd"
pattern = "abc"
index = 0
```
```text
text = "xxbaca"
pattern = "aac"
index = 3
```
```text
text = "abcdef"
pattern = "aaf"
index = -1
```
### Discussion Requirements
1. State the invariant maintained for the current fixed-length window.
2. Explain how repeated characters and exact multiplicity are handled.
3. Cover a match at index zero, the last possible index, a longer pattern, identical strings, and no match.
4. Explain why byte indexing is consistent for the ASCII contract and what must change for Unicode code points or grapheme clusters.
Quick Answer: Given a text and pattern, find the first substring whose characters match the pattern with exact multiplicity. The task assesses frequency accounting, boundary cases, and efficient string processing under a linear-time target.
Implement `firstAnagramStart(text, pattern)`.
Return the zero-based start index of the **earliest** contiguous substring of `text` whose characters form exactly the same multiset as `pattern`. Character order inside the substring may differ, but every character's multiplicity must match exactly. Return `-1` when no such substring exists.
Because every candidate substring must contain exactly as many characters as `pattern`, all candidates share one window length: `len(pattern)`.
### Output semantics
- The answer is a single integer.
- When several substrings qualify, return the **smallest** start index. The answer is therefore unique for every input.
- Return `-1` when nothing qualifies, including when `pattern` is longer than `text`.
- Comparison is exact and case-sensitive: `A` and `a` are different characters, and a space is an ordinary character that must be matched like any other.
- Matching is by multiset, not by set: a window holding the right characters in the wrong counts is not a match.
### Examples
Example 1:
```
text = "cbaebabacd"
pattern = "abc"
output = 0
```
The window `text[0:3]` is `"cba"`, a rearrangement of `"abc"`. The window `text[6:9]` is `"bac"` and also qualifies, but index 0 is earlier.
Example 2:
```
text = "xxbaca"
pattern = "aac"
output = 3
```
`pattern` needs two `a` and one `c`. The only qualifying window is `text[3:6]` = `"aca"`, which starts at the last legal index. Note that `text[2:5]` = `"bac"` contains the same *set* of letters as `"aac"` but the wrong counts, so it does not qualify.
Example 3:
```
text = "abcdef"
pattern = "aaf"
output = -1
```
No length-3 window of `text` contains two `a` characters.
### Requirements
Do not modify either input and do not materialize all candidate substrings. Aim for `O(len(text) + len(pattern))` time and `O(1)` auxiliary space, treating the 95-character printable-ASCII alphabet as a constant.
Constraints
- 1 <= len(text) <= 90000
- 1 <= len(pattern) <= 90000
- Both strings contain only printable ASCII characters from U+0020 (space) through U+007E (tilde) -- a 95-character alphabet
- Characters compare exactly and case-sensitively; 'A' and 'a' are different
- If len(pattern) > len(text), the answer is -1
- Let B be the compact UTF-8 JSON byte length of [text, pattern] (no whitespace outside strings, shortest required JSON escapes for quotation marks and reverse solidus). Inputs satisfy B <= 96000
- The result is -1 or an index below 90000, so it always fits in a 32-bit signed integer and its compact JSON encoding uses at most 5 bytes
- Target O(len(text) + len(pattern)) time and O(1) auxiliary space for the fixed 95-character alphabet
Examples
Input: ('cbaebabacd', 'abc')
Expected Output: 0
Explanation: Worked example 1 from the source: the window at index 0 is 'cba'.
Input: ('xxbaca', 'aac')
Expected Output: 3
Explanation: Worked example 2: only 'aca' at the last possible start index 3 has two a's and one c.
Hints
- Every qualifying substring has exactly len(pattern) characters, so there is only ever one window size to consider.
- Advancing the window by one position changes only two characters: one leaves on the left and one enters on the right. The rest of the frequency state is untouched.
- Rescanning both frequency tables at every position costs O(alphabet) per step. Keep a single counter of how many alphabet slots currently disagree, and update it only for the two slots that changed.