I've always wondered if Anagrams and Palindromes will ever be useful in real life. Sometimes, I think of a use case but just checking if 2 things are anagrams or palindromes doesn't really prove to be useful.

However, problems like this mess with your brain in a way that makes them fearsome and I like stuff like that which is why I respect them despite their uselessness.

Problem

Given an array of strings, group anagrams together.

Example:

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

Note:
All inputs will be in lowercase.
The order of your output does not matter.

Approach 1: The Lazy method

If you're lazy like me then you'll know that the laziest way to code if 2 strings are anagrams is to sort them and check for equality.

Algorithm:

1. Initialize a Hash Map called groups
2. Iterate through the array
3. For each string find the sorted string which is the key and append the string to the list of anagrams.
4. Return the list of all values in the hash map.

Code:

def approach1(arr):
    groups = {}

    for s in arr:
        key = ''.join(sorted(list(s)))
        groups[key] = groups.get(key, []) + [s]

    return list(groups.values())

Complexity Analysis:

Time Complexity: O(n*k*log(k)), where n is the length of arr, and k is the maximum length of a string in strs. 

Space Complexity: O(n*k), the size of the hash map

Approach 2: Paying Attention

The above approach would have worked for any kind of data where each element is quantifiable.

But in this situation our data space is limited.

We are only dealing with lowercase english alphabets. In other words, there are only 26 possible characters in each string.

So, we can use the frequency of each alphabet to uniquely group anagrams.

But, what will the key be for our new hashmap?

The array of 26 frequencies will be unique but we can't keep an array as a key in a normal hashmap(language exceptions excluded).

Until now we've used either numbers or strings as the key.
If we can transform our array into a number or a string then our problem will be solved.

What could this transformer function be?

How about constructing a string with some non-numerical character between consecutive numbers?

Now, that we know the algorithm let's code!

Code:

def approach2(arr):
    groups = {}
    for s in arr:
        freq = [0 for i in range(26)]

        for c in s:
            freq[ord(c) - ord('a')] += 1

        freq = list(map(str, freq))
        key = ':'.join(freq)

        groups[key] = groups.get(key, []) + [s]

    return list(groups.values())

Complexity Analysis:

Time Complexity: O(n*k), where n is the length of arr, and k is the maximum length of a string in strs. 

Space Complexity: O(n*k), the size of the hash map

Summary

Paying attention is very important to make those "wow" optimizations.

The replit for this problem: