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.This approach involves sorting each word in the array and comparing adjacent sorted words. If two adjacent sorted words are equal, they are anagrams and we remove the second word. Iterate through the array, adjusting the index when necessary due to removals.
This C solution defines a function that checks if two words are anagrams by sorting their characters and comparing the results. We iterate through the words array and remove adjacent anagrams. Sorting is performed with qsort, and each comparison's result dictates if we should remove a word.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m log m) where n is the number of words and m is the maximum length of a word, due to sorting each word.
Space Complexity: O(m) for each duplicated word during comparisons.
This method involves counting the frequency of each letter for the words being compared. Adjacency checks then use these frequency dictionaries (or arrays) to decide if words are anagram pairs, which leads to the removal of one.
The C solution uses a fixed-size array to count character occurrences. It removes anagrams by verifying that each letter frequency cancels out.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m) where n is number of words and m is length of longest word.
Space Complexity: O(1) due to constant space usage for the frequency arrays.
| Approach | Complexity |
|---|---|
| Sort and Compare | Time Complexity: O(n * m log m) where n is the number of words and m is the maximum length of a word, due to sorting each word. |
| Frequency Count and Compare | Time Complexity: O(n * m) where n is number of words and m is length of longest word. |
Group Anagrams - Categorize Strings by Count - Leetcode 49 • NeetCode • 611,582 views views
Watch 9 more video solutions →Practice Find Resultant Array After Removing Anagrams with our built-in code editor and test cases.
Practice on FleetCode