Find All Anagrams in a String

Find All Anagrams in a String

What is this problem about?

The Find All Anagrams in a String interview question asks you to find the starting indices of all substrings in a string s that are anagrams of a pattern string p. An anagram is a rearrangement of characters; for example, "abc" and "cba" are anagrams. You need to return a list of all matching start positions.

Why is this asked in interviews?

This is a classic problem asked by almost every top-tier tech company (Apple, Microsoft, Google, Meta). It tests your mastery of the Sliding Window interview pattern and efficient character counting. It evaluation your ability to process a string in $O(N)$ time by maintaining a frequency state rather than rebuilding the count for every possible substring.

Algorithmic pattern used

This problem uses a Fixed-size Sliding Window and a Hash Table (or frequency array).

1. Create a frequency map for the pattern p.
2. Maintain a "running" frequency map for the current window in s of length p.length().
3. As the window slides:
   • Add the character entering the window on the right.
   • Remove the character leaving the window on the left.
4. If the two maps are identical, the current start index is an anagram position.

Example explanation

s = "cbaebabacd", p = "abc"

1. Target frequency: {a:1, b:1, c:1}.
2. Initial window (idx 0-2): "cba". Frequency: {a:1, b:1, c:1}. Match! Add index 0.
3. Slide to idx 1-3: "bae". Add 'e', remove 'c'. Frequency: {a:1, b:1, e:1}. No match.
4. ... continue sliding ...
5. Window at idx 6-8: "bac". Frequency: {a:1, b:1, c:1}. Match! Add index 6. Result: [0, 6].

Common mistakes candidates make

• Inefficient map comparisons: Comparing the entire frequency map (26 characters) at every step can be optimized by using a "matches" counter that tracks how many unique characters have reached the target frequency.
• String sorting: Trying to sort every substring to check for anagrams, which makes the complexity $O(N imes M \log M)$.
• Off-by-one errors: Incorrectly handling the index when adding and removing characters from the window.

Interview preparation tip

For all anagram-related problems, a frequency array of size 26 (for lowercase English letters) is your best friend. It is much faster than a standard Hash Map and provides $O(1)$ updates and comparisons.