Find First Anagram Occurrence
DatabricksBackend Engineer · Technical ScreenLast updated
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.
Follow-up: Explain how your approach would scale if text were extremely large, streamed in chunks, or distributed across multiple machines.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.