Find First Anagram Occurrence
Company: Databricks
Role: Backend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given two strings `text` and `pattern`, return the starting index of the first substring in `text` that is an anagram of `pattern`. If no such substring exists, return `-1`.
A substring is an anagram of `pattern` if it has exactly the same character frequencies as `pattern`, possibly in a different order.
Assume the input strings contain lowercase English letters unless otherwise specified.
Example:
```text
text = "cbaebabacd"
pattern = "abc"
```
The substrings of length `3` are checked from left to right. The first substring that is an anagram of `"abc"` is `"cba"`, so the answer is `0`.
Follow-up: Explain how your approach would scale if `text` were extremely large, streamed in chunks, or distributed across multiple machines.
Quick Answer: This question evaluates proficiency in string processing, character-frequency analysis, and efficient substring search techniques, measuring competency in algorithmic reasoning and implementation for pattern matching.
Given two strings `text` and `pattern`, return the starting index of the first substring in `text` that is an anagram of `pattern`. If no such substring exists, return `-1`.
A substring is an anagram of `pattern` if it has exactly the same character frequencies as `pattern`, possibly in a different order.
Assume the input strings contain lowercase English letters unless otherwise specified.
Example:
```
text = "cbaebabacd"
pattern = "abc"
```
The substrings of length `3` are checked from left to right. The first substring that is an anagram of `"abc"` is `"cba"`, so the answer is `0`.
Use a fixed-size sliding window of length `len(pattern)`: maintain a character-frequency count for the current window and compare it against the frequency count of `pattern`. Slide one character at a time, adding the incoming character and removing the outgoing one in O(1).
Follow-up: If `text` were extremely large, streamed in chunks, or distributed across machines, the sliding window only needs O(26) state per position, so you can process the stream incrementally; for a distributed split, each shard scans its slice plus an overlap region of `len(pattern) - 1` characters from the next shard so anagrams straddling a boundary are not missed.
Constraints
- 0 <= len(text), len(pattern)
- text and pattern consist of lowercase English letters ('a'-'z')
- If pattern is empty, the answer is 0 (the empty string is an anagram of the empty pattern at index 0)
- If len(pattern) > len(text), the answer is -1
Examples
Input: ("cbaebabacd", "abc")
Expected Output: 0
Explanation: The length-3 window "cba" at index 0 is an anagram of "abc", so 0 is returned immediately.
Input: ("abab", "ab")
Expected Output: 0
Explanation: The first window "ab" is already an anagram of "ab".
Hints
- Two strings are anagrams iff they have identical character-frequency counts. Comparing 26-element count arrays is O(26).
- Only substrings of length exactly len(pattern) can be anagrams, so slide a fixed-size window across text.
- When the window moves right by one, add the entering character's count and subtract the leaving character's count instead of recomputing the whole window — that keeps each step O(1).
- Return as soon as the window's frequency array equals pattern's; if you reach the end without a match, return -1.