Problem Description
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 formed by rearranging the letters of a different word.
Key Insights
- Anagrams are words that contain the same characters in different orders.
- We can utilize a hash table to store the canonical form of each word (sorted characters).
- We only need to keep one instance of each set of anagrams as we traverse the list.
- The order of elements that remain in the resultant array is determined by their first occurrence.
Space and Time Complexity
Time Complexity: O(n * k log k), where n is the number of words and k is the maximum length of the words (for sorting). Space Complexity: O(n), for storing the resultant array.
Solution
To solve the problem, we can use a hash table (or a set) to track unique anagrams. For each word, we sort the characters to create a canonical form. We iterate through the list of words and check if the canonical form has been seen before. If it has not, we add the original word to the result list and mark the canonical form as seen.