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.The key observation in #2273 Find Resultant Array After Removing Anagrams is that you only need to remove words that are anagrams of the immediately previous word. This means you do not compare every pair of strings—only consecutive ones.
A common approach is to create a canonical representation of each word. One way is to sort the characters in the string and treat the sorted result as its signature. If two consecutive words produce the same sorted signature, they are anagrams, so the later one should be skipped. Otherwise, append the word to the resultant array.
Another optimization is to represent each word using a 26-length frequency count of characters instead of sorting, which avoids the sorting cost and can be faster for longer strings.
This method processes each word sequentially and maintains the previous signature for comparison. The overall time complexity is typically O(n * k log k) using sorting (where n is the number of words and k is the word length), with O(k) auxiliary space per comparison.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sort characters to form signature | O(n * k log k) | O(k) |
| Character frequency array comparison | O(n * k) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Instead of removing each repeating anagram, try to find all the strings in words which will not be present in the final answer.
For every index i, find the largest index j < i such that words[j] will be present in the final answer.
Check if words[i] and words[j] are anagrams. If they are, then it can be confirmed that words[i] will not be present in the final answer.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
While this exact problem may not always appear, similar anagram-based string comparison questions are common in technical interviews. Practicing this problem helps strengthen concepts around hashing, string normalization, and array traversal.
Arrays or strings are sufficient for this problem. A character frequency array of size 26 is commonly used to represent the signature of each word, enabling efficient anagram comparison.
The optimal approach compares each word with the previous one using a canonical representation. By sorting characters or using a frequency count as a signature, you can quickly detect if two adjacent words are anagrams and skip duplicates.
The problem specifically requires removing words that are anagrams of the immediately previous word. Therefore, only adjacent comparisons are necessary, which simplifies the solution and improves efficiency.