Data Structures

Given an array of strings `arr`

, return an array where all strings with the same anagram are grouped together. All the strings are made of lowercase characters "a" through "z".

We recommend solving the previous problem "Validate Anagrams" first.

First Few Test Cases:

Two strings are anagrams if every letter appears the same number of times in both of them. Here's an example, where we group the strings "baa", "aab", "cab", and so on, using this idea:

To solve this problem, you can iterate through each string. First, you find the count of each letter in the string. Afterwards, you use that information to put the string into the correct group.

We need a data structure that stores each group in a convenient way, so that you can look up a group by the count of each letter. HashMaps let you instantly lookup data based on anything, so we can use a HashMap to store each group. Here's the general idea:

That's the full solution, but there's a small implementation problem. Python doesn't let you use HashMaps as the keys to another HashMap. You can only use immutable objects as keys. We can fix this by using tuples as the keys instead. The tuples will have 26 entries corresponding to a letter a through z. Here's the above HashMap, but using tuples:

Here's the code for this:

Time Complexity $O(n \cdot m)$ worst-case, where n is the size of the Array, and m is the average size of the strings. We loop through every string in the Array $\tt n$, and for each string we create a tuple by iterating through O(m) letters (and we hash the tuple which takes another O(m) time), so this is a total of 2m * n time.

Space Complexity $O(n \cdot m)$. We return an array with n strings, each with average size m.

Mark as Completed: