Find the First Anagram Window in a String

Question

The question asks the candidate to implement a function that finds the first occurrence of an anagram of a given string within another string.

Codemia · Accepted Answer

To find the first anagram window in a string, we can use the sliding window technique combined with a hash map to keep track of character counts. The idea is to maintain a window of the size of the target string and compare character counts within this window to the target string's character counts.

1. Create a hash map to count the frequency of characters in the target string.
2. Initialize two pointers for the sliding window: `start` and `end`.
3. Expand the `end` pointer to include characters in the window until its size matches the target string.
4. Compare the character counts in the current window to the target string's counts. If they match, return the `start` index.
5. If they do not match, slide the `start` pointer to the right and adjust the counts accordingly.

The time complexity of this approach is O(n), where n is the length of the input string. This is because we traverse the string with the sliding window at most twice. The space complexity is O(1) since the hash map will have a fixed size based on the character set (e.g., 26 for lowercase letters).

```python
from collections import Counter

def find_anagram_window(s: str, target: str) -> int:
    target_count = Counter(target)
    window_count = Counter()
    target_length = len(target)

for end in range(len(s)):
        window_count[s[end]] += 1
        if end >= target_length:
            start_char = s[end - target_length]
            if window_count[start_char] == 1:
                del window_count[start_char]
            else:
                window_count[start_char] -= 1

if window_count == target_count:
            return end - target_length + 1

return -1
```
This code defines a function that returns the starting index of the first anagram of `target` found in `s`, or -1 if none exists.

Consider edge cases such as when either string is empty. If the target string is empty, the function should return 0, as an empty string is considered an anagram of any string. If the input string is shorter than the target string, return -1 immediately.

Find the First Anagram Window in a String

Databricks

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Databricks Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string