49. Group Anagrams - Explanation

Description

Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Example 1:

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

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

Example 2:

Input: strs = ["x"]

Output: [["x"]]

Example 3:

Input: strs = [""]

Output: [[""]]

Constraints:

1 <= strs.length <= 1000.
0 <= strs[i].length <= 100
strs[i] is made up of lowercase English letters.

Recommended Time & Space Complexity

You should aim for a solution with O(m * n) time and O(m) space, where m is the number of strings and n is the length of the longest string.

Hint 1

A naive solution would be to sort each string and group them using a hash map. This would be an O(m * nlogn) solution. Though this solution is acceptable, can you think of a better way without sorting the strings?

Hint 2

By the definition of an anagram, we only care about the frequency of each character in a string. How is this helpful in solving the problem?

Hint 3

We can simply use an array of size O(26), since the character set is a through z (26 continuous characters), to count the frequency of each character in a string. Then, we can use this array as the key in the hash map to group the strings.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Sorting

Intuition

Anagrams become identical when their characters are sorted.
For example, "eat", "tea", and "ate" all become "aet" after sorting.
By using the sorted version of each string as a key, we can group all anagrams together.
Strings that share the same sorted form must be anagrams, so placing them in the same group is both natural and efficient.

Algorithm

Create a hash map where each key is the sorted version of a string, and the value is a list of strings belonging to that anagram group.
Iterate through each string in the input list:
- Sort the characters of the string to form a key.
- Append the original string to the list corresponding to this key.
After processing all strings, return all values from the hash map, which represent the grouped anagrams.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)
        for s in strs:
            sortedS = ''.join(sorted(s))
            res[sortedS].append(s)
        return list(res.values())

Time & Space Complexity

Time complexity: $O(m * n \log n)$
Space complexity: $O(m * n)$

Where $m$ is the number of strings and $n$ is the length of the longest string.

2. Hash Table

Intuition

Instead of sorting each string, we can represent every string by the frequency of its characters.
Since the problem uses lowercase English letters, a fixed-size array of length 26 can capture how many times each character appears.
Two strings are anagrams if and only if their frequency arrays are identical.
By using this frequency array (converted to a tuple so it can be a dictionary key), we can group all strings that share the same character counts.

Algorithm

Create a hash map where each key is a 26-length tuple representing character frequencies, and each value is a list of strings belonging to that anagram group.
For each string in the input:
- Initialize a count array of size 26 with all zeros.
- For each character c in the string, increment the count at the corresponding index.
- Convert the count array to a tuple and use it as the key.
- Append the string to the list associated with this key.
After processing all strings, return all the lists stored in the hash map.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            res[tuple(count)].append(s)
        return list(res.values())

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity:
- $O(m)$ extra space.
- $O(m * n)$ space for the output list.

Where $m$ is the number of strings and $n$ is the length of the longest string.

Common Pitfalls

Using a Mutable Key Type for the Hash Map

When using character frequency arrays as keys, you must convert them to an immutable type (like a tuple in Python or a string in other languages). Lists and arrays are mutable and cannot be used as dictionary keys directly.

# Wrong: using list as key
count = [0] * 26
res[count].append(s)  # TypeError: unhashable type 'list'

# Correct: convert to tuple
res[tuple(count)].append(s)

Assuming Input Contains Only Lowercase Letters

The frequency array approach with size 26 only works for lowercase English letters. If the input could contain uppercase letters or other characters, the solution would fail or produce incorrect groupings.

# Wrong: will crash on uppercase
count[ord(c) - ord('a')] += 1  # Negative index for uppercase

# Should validate or handle: ord('A') - ord('a') = -32

Creating a New Key Format That Has Collisions

When converting frequency counts to strings, using a naive format like concatenation without separators can cause collisions. For example, counts [1,11] and [11,1] could produce the same string "111".

# Wrong: potential collisions
key = ''.join(str(c) for c in count)  # "111" for both [1,11] and [11,1]

# Correct: use separator
key = ','.join(str(c) for c in count)  # "1,11" vs "11,1"