Find Resultant Array After Removing Anagrams

Find Resultant Array After Removing Anagrams

What is this problem about?

The Find Resultant Array After Removing Anagrams interview question is a string filtering task. You are given an array of words. You need to remove a word if it is an anagram of the word immediately preceding it. You repeat this until no word is an anagram of its left neighbor. The goal is to return the final list of words.

Why is this asked in interviews?

Companies like Meta and Amazon ask this to test your ability to implement simple string comparisons and "Simulation" logic. It evaluates if you understand that an anagram check can be performed efficiently by sorting the characters of a word or using a frequency map. It’s a core Hash Table interview pattern for entry-level developers.

Algorithmic pattern used

This problem uses Linear Scan and String Normalization.

1. Initialize: Create a result list and add the first word.
2. Iterate: Start from the second word in the input array.
3. Anagram Check: Compare the current word with the most recently added word in the result list.
   • A common way to check anagrams is to sort both strings: sorted(s1) == sorted(s2).
4. Action: If they are NOT anagrams, add the current word to the result list. If they are anagrams, skip the current word.

Example explanation

Words: ["abba", "baba", "bbaa", "cd", "dc"]

1. Add "abba". Result: ["abba"].
2. "baba" vs "abba": Anagrams! Skip.
3. "bbaa" vs "abba": Anagrams! Skip.
4. "cd" vs "abba": Not anagrams. Add "cd". Result: ["abba", "cd"].
5. "dc" vs "cd": Anagrams! Skip. Final Result: ["abba", "cd"].

Common mistakes candidates make

• Global Anagrams: Trying to remove all anagrams in the array regardless of position. The rule only applies to adjacent words.
• Inefficient Check: Sorting the strings repeatedly inside the loop. While fine for small words, for very long strings, a frequency array of size 26 is faster.
• Reference Error: Comparing the current word to the original array's previous word instead of the result list's last word (though in this specific problem, both usually work).

Interview preparation tip

Always clarify the "Anagram" definition. While standard, some interviewers might add rules about case sensitivity or special characters. Using a helper function isAnagram(s1, s2) makes your code more modular and easier to read.