Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

 

Constraints:

1 <= strs.length <= 104

0 <= strs[i].length <= 100

strs[i] consists of lowercase English letters.

My thought process:

Anagrams are basically strings that has the exact distribution of characters as another string. 

Therefore, we need to find the distribution of characters of each word in order to group them finally in the output list. Hence, we need to use a loop to iterate the entire input array and count occurrence of each character. We can use a dictionary in python to store the count of characters. For example, the string 'eat' will have the dictionary { 'e':1, 'a':1, 't':1 }

When iterating through each string and counting occurrence of each character, we also need to be able to know if we had gone past the same distribution of characters before and also insert this inside a list or another data structure? When it comes to knowing if a value already exists or not hashmap comes instantly in my mind! 

Hence, we can use a hashmap to store the strings with same character distribution where hashmap is the key and list of strings is the value, e.g: { 'e':1, 'a':1, 't':1 }->['eat','tea','ate']. 

BUT WAIT! We CANNOT USE A HASHMAP AS A KEY OF ANOTHER HASHMAP!

Using a dictionary as a key of another dictionary will give us this error:  
TypeError: unhashable type: 'dict'

What else can we use as a unique key of dictionary in python? Strings, numbers, and tuples can be used as keys in python dictionaries since they are immutable. Can I convert the dictionary to a string? Yes, we can use str({ 'e':1, 'a':1, 't':1 }} but this won't solve the problem because the converted string will not be unique and will vary for different strings of same anagram. This is because dictionaries are not sorted by default in python. The string 'eat' will give us the dictionary { 'e':1, 'a':1, 't':1 } while the string 'tea' will give us the dictionary {'t':1,'e':1,'a':1}. 

Can we convert it to a unique number? Nothing comes to my mind.

Can we convert it to a unique tuple? Nothing still comes to my mind. ({'e':1,'a':1,'t':1}) will be different from ({'t':1,'e':1,'a':1}). 

As we can see, the problem lies in the dictionary not being sorted. So do we sort it? sorting a dictionary using sorted() will result in creating a list of the keys from that dictionary. We need to do something else. We need immutable unique keys for each anagram. 

If we carefully look at the question we can see that the input will only consist of lowercase English letters(a-z). Hence, we don't need to use dictionary to store the count of letters. We can use a list of length 26 to store the count of letters using the numerical difference between the letter and ASCII 'a' to determine its index in the list. 

We can use ord() to get the integer that represents the Unicode character. Example: [ord(character)-ord('a')] += 1. Later on, we can convert this list to a tuple to use it as immutable keys for our dictionary. 

Now let's code the solution:

What lesson did I learn from this problem?
READ THE DAMN QUESTION PROPERLY!