Group Anagrams

Problem Statement

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.

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

You should aim for a solution with O(m \cdot 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 \cdot n \log n) 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.

Solution

Sorting

from collections import defaultdict


def group_anagrams(strs: list[str]) -> list[list[str]]:
    anagram_groups = defaultdict(list)
    for s in strs:
        sorted_s = "".join(sorted(s))
        anagram_groups[sorted_s].append(s)
    return list(anagram_groups.values())

Time complexity: O(m \cdot n \log n) Space complexity: O(m \cdot n)

Hash Table

from collections import defaultdict


def group_anagrams(strs: list[str]) -> list[list[str]]:
    anagram_groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord("a")] += 1
        anagram_groups[tuple(count)].append(s)
    return list(anagram_groups.values())

Time complexity: O(m \cdot n) Space complexity: O(m)