Find All Anagrams in a String

Question

Given strings s and p, find all start indices of p's anagrams in s. Tests sliding window with character frequency counting, a common Google phone screen question.

Codemia · Accepted Answer

To solve the problem of finding all start indices of anagrams of string `p` in string `s`, we can utilize the **sliding window** technique combined with **character frequency counting**. This approach is effective here because:

1. An anagram will have the same character frequency as the original string `p`. 
2. By maintaining a sliding window of size equal to `p` while traversing `s`, we can compare the frequency of characters in the current window with that of `p` efficiently.
3. Adjusting the window allows us to check for anagrams without generating all permutations, leading to a more efficient solution.

1. **Initialize**: Create a frequency count for the string `p` using a dictionary (or array) to store the count of each character.
2. **Setup Sliding Window**: Create a sliding window of the same length as `p` and initialize a frequency count for this window.
3. **Iterate through `s`**: Start from the beginning of `s` and slide the window right by one character at a time. For each step, update the counts by adding the new character and removing the character that is no longer in the window.
4. **Check for Anagram**: After updating the window, compare the frequency count of the window with that of `p`. If they match, record the starting index.
5. **Return Results**: Collect all valid starting indices into a result list and return it.

**Example**: For `s = 'cbaebabacd'` and `p = 'abc'`, the sliding window will iterate over:  
- 'cba' (index 0) -> is an anagram.  
- 'bae' (index 1) -> is an anagram.  
- 'aeb' (index 2) -> is an anagram.  
- 'eba' (index 3) -> not an anagram.  
- 'bac' (index 4) -> is an anagram.

```python
from collections import Counter

def find_anagrams(s, p):
    p_count = Counter(p)  # Count frequency of characters in p
    s_count = Counter()
    result = []
    p_length = len(p)

for i in range(len(s)):
        s_count[s[i]] += 1  # Add current character to the window
        # Remove the character that is left out of the window
        if i >= p_length:
            left_char = s[i - p_length]
            if s_count[left_char] == 1:
                del s_count[left_char]  # Remove it completely if count is 1
            else:
                s_count[left_char] -= 1

# Compare counts when we have a full window
        if s_count == p_count:
            result.append(i - p_length + 1)  # Append start index of anagram

return result
```

The time complexity of this approach is **O(n)**, where `n` is the length of the string `s`. This efficiency results from the single pass through `s` as we maintain and compare character counts. The space complexity is **O(1)** since the size of the frequency count dictionary is limited to a fixed number of characters (26 for lowercase English letters).

1. **Empty Strings**: If both `s` and `p` are empty, the output should be `[0]` since an empty string is an anagram of itself.
2. **No Anagram Found**: If `s` does not contain any anagrams of `p`, the result should be an empty list `[]`.
3. **s shorter than p**: If the length of `s` is less than `p`, the result should also be `[]` since it's impossible to find an anagram.
4. **Repeated Characters**: If `p` consists of repeated characters (e.g., `p = 'aaa'`), ensure that the algorithm correctly identifies all valid starting indices in `s` that match this frequency.

Find All Anagrams in a String

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Google 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