This Anagram problem was asked at Amazon technical interview!

As you already know about anagrams, let’s do more exploration on how anagram concepts are used in testing how well you know the operations of dictionary and array. Even this concept is being used in the interview on Amazon.

The problem is simply stated as the following:

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

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

Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

Since anagram words consist of the same characters but in a different order, what we can do is map out each of the characters in the strings. We can use a strategy that represents each character within an array where each index represents a number in the alphabet. Later, this can be mapped out to the actual character, with the value of each index indicating whether the alphabet is present in the original string: 0 if it is not, and 1 if it is.

For example:

"eat" = [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]

The mapped out value can be used as the key of the dictionary that we will use.

Hence, the algorithm would be

1. Define a hashmap/dictionary
2. Iterate each strings
3. While iterating, define an array that will represents of the mapping of each characters
4. Create other loop inside the previous loop to fill the mapping of the character of the original string
5. Since the mapping in the form array, we can’t use it as the key of the dictionary, so, convert the array to tuple
6. Verify, if the key exists in the dictionary, if not then set the key with the value of empty array
7. Append the current string to the dictionary with the mapping as the key
8. Since, the output that we want is List[List[str]] , we need to get the values from the hashmap/dictionary

Hence, my solution would be

# Time Complexity: O(N) | Space Complexity: O(1)
class Solution:
 def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
  answer = {} # Step 1
  
  for s in strs: # Step 2
   mapping = [0] * 26 # Step 3
   
   for char in s: # Step 4
    mapping[ord(char) - ord('a')] += 1 
   
   key = tuple(mapping) # Step 5
   if not answer.get(key, 0): # Step 6
    answer[key] = []
   answer[key].append(s) # Step 7
   
  return list(answer.values()) # Step 8

Let me know if you need further explanation by comment down below!