Group Anagrams

Tags

Group Anagrams

Category

Strings

Difficulty

Medium

Problem Statement

Given an array of strings, group the anagrams together. Two strings are anagrams if they contain the same characters with the same frequencies, just in a different order. Return a list of groups where each group contains strings that are anagrams of each other.

Intuition

Two strings are anagrams if and only if their sorted character representations are identical. By sorting each string and using the sorted version as a key, we can efficiently bucket all anagrams together in a hash map. Alternatively, we can use a character frequency count as the key, which avoids the sorting cost per string.

Approach

  1. Initialize an empty hash map where keys are sorted strings (or character frequency tuples) and values are lists of original strings.
  2. Iterate through each string in the input array.
  3. For each string, sort its characters to produce a canonical key.
  4. Append the original string to the list stored at that key in the hash map.
  5. Return all the values (lists) from the hash map.

Pseudocode

function groupAnagrams(strings):
    groups = {}
    for each string in strings:
        key = sort(string)
        if key not in groups:
            groups[key] = []
        groups[key].append(string)
    return values of groups

Time & Space Complexity

  • Time: O(n * k * log(k)) where n is the number of strings and k is the maximum length of a string. Sorting each string takes O(k log k).
  • Space: O(n * k) to store all strings in the hash map.

Using character frequency counts as keys instead: O(n * k) time, since counting characters is O(k) per string.

Key Insights

  • Sorting provides a canonical form that is identical for all anagrams.
  • A character frequency tuple (e.g., count of each letter a-z) can also serve as a hash key and avoids sorting.
  • The hash map naturally partitions strings into anagram groups in a single pass.

Edge Cases

  • Empty input array: return an empty list.
  • Single-character strings: each is its own anagram group unless duplicates exist.
  • Strings of different lengths: they can never be anagrams, so they naturally fall into separate groups.
  • Empty strings: all empty strings are anagrams of each other and should be grouped together.
  • Duplicate strings: duplicates are anagrams and belong in the same group.

Linked mentions