Find First Anagram Occurrence
Company: Databricks
Role: Backend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
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".
Input: ("af", "be")
Expected Output: -1
Explanation: No window has the same character frequencies as "be".
Input: ("", "a")
Expected Output: -1
Explanation: text is empty and shorter than pattern, so no anagram exists.
Input: ("a", "")
Expected Output: 0
Explanation: An empty pattern matches at index 0 by convention.
Input: ("hello", "oll")
Expected Output: 2
Explanation: Windows "hel", "ell" do not match; "llo" at index 2 is an anagram of "oll".
Input: ("baa", "aa")
Expected Output: 1
Explanation: Window "ba" at index 0 is not an anagram; "aa" at index 1 is.
Input: ("abc", "abcd")
Expected Output: -1
Explanation: pattern is longer than text, so no window of the required length exists.
Input: ("xyzabc", "cba")
Expected Output: 3
Explanation: The first matching window "abc" begins at index 3; earlier windows do not match "cba"'s frequencies.
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.