Data Structures

Given an array of strings `arr`

, return an array where all strings with the same anagram are grouped together.

First Few Test Cases:

Two strings are anagrams if every letter appears the same number of times in 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 count each letter in the string, and then you use that information to put the string in the correct group.

We need a data structure that stores each group, and it should let you 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: