Watch 10 video solutions for Find Resultant Array After Removing Anagrams, a easy level problem involving Array, Hash Table, String. This walkthrough by codestorywithMIK has 4,869 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed string array words, where words[i] consists of lowercase English letters.
In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i] are anagrams, and delete words[i] from words. Keep performing this operation as long as you can select an index that satisfies the conditions.
Return words after performing all operations. It can be shown that selecting the indices for each operation in any arbitrary order will lead to the same result.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".
Example 1:
Input: words = ["abba","baba","bbaa","cd","cd"] Output: ["abba","cd"] Explanation: One of the ways we can obtain the resultant array is by using the following operations: - Since words[2] = "bbaa" and words[1] = "baba" are anagrams, we choose index 2 and delete words[2]. Now words = ["abba","baba","cd","cd"]. - Since words[1] = "baba" and words[0] = "abba" are anagrams, we choose index 1 and delete words[1]. Now words = ["abba","cd","cd"]. - Since words[2] = "cd" and words[1] = "cd" are anagrams, we choose index 2 and delete words[2]. Now words = ["abba","cd"]. We can no longer perform any operations, so ["abba","cd"] is the final answer.
Example 2:
Input: words = ["a","b","c","d","e"] Output: ["a","b","c","d","e"] Explanation: No two adjacent strings in words are anagrams of each other, so no operations are performed.
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 10words[i] consists of lowercase English letters.Problem Overview: You are given an array of words. If two adjacent words are anagrams, remove the later one. Continue scanning left to right and keep only the first occurrence in each consecutive anagram group. The final result is the array of remaining words after these removals.
Approach 1: Sort and Compare (Time: O(n * k log k), Space: O(k))
The most common strategy is to normalize each word so all anagrams share the same representation. Sort the characters of every word using sort(). Two strings are anagrams if their sorted forms are identical. Iterate through the array once, compute the sorted version of the current word, and compare it with the sorted version of the previously accepted word. If they match, skip the current word; otherwise append it to the result array. Sorting each string costs O(k log k) where k is the word length, and you perform this for n words, resulting in O(n * k log k) time. Space usage stays O(k) for the temporary sorted representation. This approach is simple, reliable, and commonly used for string anagram detection problems.
Approach 2: Frequency Count and Compare (Time: O(n * k), Space: O(26))
A more efficient approach avoids sorting entirely. Instead, build a frequency vector for each word representing counts of characters a–z. Two words are anagrams if their frequency arrays match exactly. While iterating through the input, compute the frequency array for the current word and compare it with the frequency array of the last accepted word. If the arrays are identical, the current word is an anagram of the previous one and should be skipped. Otherwise add it to the result and update the stored frequency array. Counting characters requires O(k) time per word, so the full traversal runs in O(n * k). Space complexity remains O(26) (constant) for the frequency vector. This technique is common in problems involving hash tables or character counting and avoids the overhead of sorting.
Both approaches rely on the same insight: you only compare the current word with the previously kept word, not with the entire result array. The constraint that removals happen only for adjacent anagrams simplifies the logic to a single linear pass over the array.
Recommended for interviews: The frequency-count solution is usually preferred because it improves the complexity from O(n * k log k) to O(n * k). Still, explaining the sorting approach first demonstrates understanding of the classic sorting-based anagram check. Transitioning to frequency counting shows optimization and stronger algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Compare | O(n * k log k) | O(k) | Simple implementation and common approach when checking anagrams with sorting |
| Frequency Count and Compare | O(n * k) | O(26) | Optimal solution when words contain lowercase letters and sorting overhead should be avoided |