Find Resultant Array After Removing Anagrams - Leetcode Solution

Problem Statement:

You are given an array of strings. You have to find the resultant array of strings after removing all the anagrams from the array.

Approach:

The first and most important thing to do is to understand what an anagram is. An anagram is a word or phrase formed by rearranging the letters of another, such as cinema, formed from iceman.

One approach to solve this problem is to create a dictionary/hash table with the characters of each string sorted in alphabetical order as the key, and the list of strings that share the same sorted characters as the value.

For example, consider the input array ["eat", "tea", "tan", "ate", "nat", "bat"]. If we sort the characters of each string in alphabetical order, we get:

"eat" -> "aet" "tea" -> "aet"

"tan" -> "ant" "ate" -> "aet"

"nat" -> "ant"

"bat" -> "abt"

If we create a dictionary using these sorted strings as keys and the original strings as the values, we get:

{ "aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"] }

Now, we can simply iterate over the values of the dictionary and add only those lists to the resultant array that have a length of 1.

In the above example, the final resultant array would be:

["bat"]

Complexity Analysis:

Let n be the length of the input array, and k be the maximum length of a string in the array.

Time complexity: The time complexity of the above solution is O(nklog(k)), where k*log(k) is the time taken to sort each string in alphabetical order.

Space complexity: The space complexity of the above solution is O(nk), where nk is the space taken to store the dictionary.

1