In this problem, we are given a list of strings and need to group all anagrams together.

An anagram is a word that has the same characters as another word, but possibly in a different order. For example, "act"and "cat" are anagrams because both contain the letters a, c, and t.

Problem

Given an array of strings strs, group all anagrams together into sublists.

Example:

Input: strs = ["act","pots","tops","cat","stop","hat"]

Output: [["hat"], ["act", "cat"], ["pots", "tops", "stop"]]

The order of the groups does not matter.

Approach 1: Sorting Each String

The main idea is that anagrams become the same string after sorting.

For example:

"act" -> "act"
"cat" -> "act"
"pots" -> "opst"
"tops" -> "opst"
"stop" -> "opst"

So we can use the sorted version of each string as a key in a hash map. Every word with the same sorted key belongs in the same group.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        seen = defaultdict(list)

        for s in strs:
            sortedS = ''.join(sorted(s))
            seen[sortedS].append(s)

        return list(seen.values())

Explanation

We create a hash map called seen, where each key is the sorted version of a string, and each value is a list of words that match that sorted version.

For each string s in strs, we sort it and store it in sortedS. Then we append the original string to the list for that key.

At the end, we return all the grouped values from the hash map.

Complexity

Let n be the number of strings, and let m be the maximum length of a string.

Sorting each string takes O(m log m), and we do this for all n strings.

Time complexity:

O(n * m log m)

Space complexity:

O(n * m)

Approach 2: Character Count

Since the strings only contain lowercase English letters, we can count how many times each letter appears.

For example:

"cat" -> [1, 0, 1, 0, ..., 1, ...]
"act" -> [1, 0, 1, 0, ..., 1, ...]

Both strings produce the same count array, so they are anagrams.

Because lists cannot be used as dictionary keys in Python, we convert the count list into a tuple.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        seen = defaultdict(list)

        for s in strs:
            count = [0] * 26

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

            seen[tuple(count)].append(s)

        return list(seen.values())

Explanation

We create a list of size 26 for each word, where each index represents a lowercase English letter.

For every character c, we calculate its position using:

ord(c) - ord('a')

Then we increment the count at that index.

After counting all characters, we convert the list into a tuple and use it as the key in the hash map.

All anagrams will have the same character-count tuple, so they will be grouped together.

Complexity

Let n be the number of strings, and let m be the maximum length of a string.

For each string, we count its characters in O(m) time.

Time complexity:

O(n * m)

Space complexity:

O(n * m)

Which Approach Is Better?

The sorting approach is easier to understand and is often good enough.

The character-count approach is more efficient because it avoids sorting. Since we only have lowercase English letters, the count array has a fixed size of 26, making this approach very clean and fast.

Final Thoughts

This problem is a great example of using a hash map to group items by a shared pattern.

The key insight is to find a common representation for anagrams. We can either sort the string or count the frequency of each character. Once we have that representation, grouping becomes simple.