9  Group Anagrams

Rank 7 · Pattern: canonical representation as a hash key · Target: about \(O(nk\log k)\) time

9.1 Problem definition

Given an array of strings, partition the strings into groups so that two strings share a group exactly when they contain the same characters with the same frequencies.

9.2 Clarifying questions

  1. Does the order of the groups or the strings within each group matter?
  2. Is anagram matching case-sensitive?
  3. What does “character” mean in the chosen language for Unicode input?
  4. Are empty strings and repeated identical strings allowed?
  5. Can the array or any word be null?

9.3 Sample answers

  1. No. Group order and order within a group are not part of correctness.
  2. Yes. Uppercase and lowercase letters are distinct.
  3. Use the language’s natural character iteration: Java UTF-16 char values, Python Unicode code points, or Rust char values.
  4. Yes. Empty strings belong together, and every repeated input string remains in the output.
  5. No. The array and every word are non-null.

9.4 Data structures and APIs

Each implementation maps a sorted-character key to a growable group of original words.

LinkedHashMap<String,List<String>> preserves first-key insertion order for deterministic display. Arrays.sort(char[]) creates the key from UTF-16 code units.

List<String> group = groupByKey.get(key);
if (group == null) {
    group = new ArrayList<>();
    groupByKey.put(key, group);
}
group.add(word);

The explicit lookup form is easy to derive in an interview: find the group, create it when absent, then append.

A defaultdict(list) creates missing groups. "".join(sorted(word)) creates a string key from Unicode code points; dictionaries preserve insertion order, although correctness does not require it.

HashMap<Vec<char>,Vec<String>> uses a sorted character vector directly as the key. entry(key).or_insert_with(Vec::new) creates missing groups; map iteration order is intentionally unspecified.

eat -> [a,e,t] -> "aet" ┐
tea -> [a,e,t] -> "aet" ├-> [eat, tea, ate]
ate -> [a,e,t] -> "aet" ┘
tan -> [a,n,t] -> "ant" ---> [tan, nat]

9.5 Approach and invariant

Pairwise anagram comparisons repeat work and can approach \(O(n^2)\). Instead, compute one canonical key per word.

For each word, sort its characters, create a canonical key, and append the original word to that key’s group.

Invariant: after processing any prefix of the input, two processed words are in the same map bucket exactly when their sorted-character keys are equal.

9.6 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class GroupAnagramsSolution {
    static List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groupByKey = new LinkedHashMap<>();
        for (String word : words) {
            char[] letters = word.toCharArray();
            Arrays.sort(letters);
            String key = new String(letters);
            List<String> group = groupByKey.get(key);
            if (group == null) {
                group = new ArrayList<>();
                groupByKey.put(key, group);
            }
            group.add(word);
        }
        return new ArrayList<>(groupByKey.values());
    }

    @Test public void emptyInputProducesNoGroups() {
        assertTrue(groupAnagrams(new String[0]).isEmpty());
    }

    @Test public void createsSingletonGroup() {
        assertGroups(
            List.of(List.of("cat")),
            groupAnagrams(new String[] {"cat"})
        );
    }

    @Test public void groupsTwoAnagrams() {
        assertGroups(
            List.of(List.of("eat", "tea")),
            groupAnagrams(new String[] {"eat", "tea"})
        );
    }

    @Test public void separatesDifferentCharacterMultisets() {
        assertGroups(
            List.of(List.of("ab", "ba"), List.of("abc")),
            groupAnagrams(new String[] {"ab", "ba", "abc"})
        );
    }

    @Test public void groupsStandardExample() {
        assertGroups(
            List.of(
                List.of("eat", "tea", "ate"),
                List.of("tan", "nat"),
                List.of("bat")
            ),
            groupAnagrams(
                new String[] {"eat", "tea", "tan", "ate", "nat", "bat"})
        );
    }

    @Test public void handlesEmptyStrings() {
        assertGroups(
            List.of(List.of("", "")),
            groupAnagrams(new String[] {"", ""})
        );
    }

    @Test public void handlesRepeatedLettersAndDifferentLengths() {
        assertGroups(
            List.of(List.of("aab", "aba", "baa"), List.of("abb"), List.of("a")),
            groupAnagrams(new String[] {"aab", "aba", "baa", "abb", "a"})
        );
    }

    @Test public void comparesLettersCaseSensitively() {
        assertGroups(
            List.of(List.of("a"), List.of("A")),
            groupAnagrams(new String[] {"a", "A"})
        );
    }

    private static void assertGroups(
            List<List<String>> expected, List<List<String>> actual) {
        assertEquals(canonicalGroups(expected), canonicalGroups(actual));
    }

    private static List<List<String>> canonicalGroups(
            List<List<String>> groups) {
        List<List<String>> canonical = new ArrayList<>();
        for (List<String> group : groups) {
            List<String> sortedGroup = new ArrayList<>(group);
            Collections.sort(sortedGroup);
            canonical.add(sortedGroup);
        }
        canonical.sort(GroupAnagramsSolution::compareGroups);
        return canonical;
    }

    private static int compareGroups(List<String> left, List<String> right) {
        int sharedSize = Math.min(left.size(), right.size());
        for (int i = 0; i < sharedSize; i++) {
            int comparison = left.get(i).compareTo(right.get(i));
            if (comparison != 0) {
                return comparison;
            }
        }
        return Integer.compare(left.size(), right.size());
    }

    public static void main(String[] args) {
        JUnitCore.main("GroupAnagramsSolution");
    }
}
import unittest
from collections import defaultdict


def group_anagrams(words):
    groups_by_key = defaultdict(list)

    for word in words:
        key = "".join(sorted(word))
        groups_by_key[key].append(word)

    return list(groups_by_key.values())


def canonical_groups(groups):
    return sorted(sorted(group) for group in groups)


class GroupAnagramsTests(unittest.TestCase):
    def assert_groups_equal(self, expected, actual):
        self.assertEqual(canonical_groups(expected), canonical_groups(actual))

    def test_empty_input(self):
        self.assertEqual([], group_anagrams([]))

    def test_groups_two_anagrams(self):
        self.assert_groups_equal(
            [["eat", "tea"]],
            group_anagrams(["eat", "tea"]),
        )

    def test_groups_standard_example(self):
        self.assert_groups_equal(
            [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]],
            group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]),
        )

    def test_handles_empty_strings(self):
        self.assert_groups_equal([["", ""]], group_anagrams(["", ""]))

    def test_handles_repeated_letters(self):
        self.assert_groups_equal(
            [["aab", "aba", "baa"], ["abb"], ["a"]],
            group_anagrams(["aab", "aba", "baa", "abb", "a"]),
        )

    def test_compares_letters_case_sensitively(self):
        self.assert_groups_equal([["a"], ["A"]], group_anagrams(["a", "A"]))


if __name__ == "__main__":
    unittest.main()
use std::collections::HashMap;

pub fn group_anagrams(words: Vec<String>) -> Vec<Vec<String>> {
    let mut groups_by_key = HashMap::new();

    for word in words {
        let mut key: Vec<char> = word.chars().collect();
        key.sort();
        groups_by_key.entry(key).or_insert_with(Vec::new).push(word);
    }

    groups_by_key.into_values().collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    fn strings(words: &[&str]) -> Vec<String> {
        words.iter().map(|word| word.to_string()).collect()
    }

    fn canonical(mut groups: Vec<Vec<String>>) -> Vec<Vec<String>> {
        for group in &mut groups {
            group.sort();
        }
        groups.sort();
        groups
    }

    #[test]
    fn empty_input() {
        assert!(group_anagrams(Vec::new()).is_empty());
    }

    #[test]
    fn groups_two_anagrams() {
        assert_eq!(
            canonical(vec![strings(&["eat", "tea"])]),
            canonical(group_anagrams(strings(&["eat", "tea"])))
        );
    }

    #[test]
    fn groups_standard_example() {
        let expected = vec![
            strings(&["eat", "tea", "ate"]),
            strings(&["tan", "nat"]),
            strings(&["bat"]),
        ];
        let input = strings(&["eat", "tea", "tan", "ate", "nat", "bat"]);
        assert_eq!(canonical(expected), canonical(group_anagrams(input)));
    }

    #[test]
    fn handles_empty_strings() {
        let expected = vec![strings(&["", ""])];
        assert_eq!(
            canonical(expected),
            canonical(group_anagrams(strings(&["", ""])))
        );
    }

    #[test]
    fn compares_letters_case_sensitively() {
        let expected = vec![strings(&["a"]), strings(&["A"])];
        assert_eq!(
            canonical(expected),
            canonical(group_anagrams(strings(&["a", "A"])))
        );
    }
}

The Java LinkedHashMap is for deterministic display only; none of the solutions relies on group order for correctness.

9.7 High-value tests

Input Expected grouping Purpose
eat, tea, tan, ate, nat, bat 3 groups standard case
"", "" one group empty strings
a one singleton one word
ab, ba, abc two groups different lengths
aab, aba, baa, abb 2 groups repeated letters

When output order is unspecified, production tests should normalize groups before comparison rather than depend on map iteration order.

9.8 Complexity and correctness

Let \(n\) be the number of words and \(k\) the maximum word length. Sorting each word costs \(O(k\log k)\), so time is \(O(nk\log k)\). Keys, groups, and output references require \(O(nk)\) character/reference storage in aggregate.

Sorting preserves exactly the multiset of characters. Therefore anagrams produce equal keys, and equal sorted keys prove equal character counts. Map bucketing is consequently both sound and complete.

9.9 If the interviewer pushes

  • For lowercase English letters only, use a 26-count key for \(O(nk)\) time. Build an unambiguous key such as #1#0#2..., not concatenated bare counts.
  • Preserve no ordering with HashMap; preserve sorted group order with a TreeMap, paying \(O(\log g)\) per key operation.
  • Normalize case or Unicode only if the contract defines those equivalences.
  • For very long words, frequency keys avoid sorting and reduce CPU cost.

9.10 TDD interview script

Confirm that both group order and order within a group are irrelevant, comparison is case-sensitive under the chosen character semantics, empty and repeated strings are allowed, and inputs are valid strings. Then write this test list:

  1. Empty input
  2. One word
  3. Two anagrams
  4. Different character multisets
  5. Standard example
  6. Empty strings
  7. Repeated letters
  8. Case sensitivity

Use a test helper that sorts words within copied groups and then sorts the copied groups. This keeps assertions order-insensitive without modifying the actual result, while preserving duplicate strings. Add one focused test, observe red, make the smallest general change, run the whole example, and refactor only while green.

From book/src, run:

./java/run.sh GroupAnagramsSolution
./python/run.sh group_anagrams_solution
./rust/run.sh group_anagrams_solution

Explain the design transition when the first anagram pair appears: rather than compare every pair of words, compute one canonical representation per word and use it as a map key.

9.10.1 Pseudocode

groupByKey = empty map from string to list of strings

for each word:
    letters = characters of word
    sort letters
    key = string made from letters
    if key has no group:
        create an empty group for key
    append the original word to that group

return all map groups

The invariant is: after any input prefix, two processed words occupy the same bucket exactly when their sorted-character keys are equal.

9.10.2 TDD sequence

Step Test code added Production code added or changed
1. No words emptyInputProducesNoGroups Introduce the grouping map and return its initially empty values.
2. First bucket createsSingletonGroup Create a bucket for a word’s key and append the original word. Add the order-insensitive assertion helper.
3. Shared canonical key groupsTwoAnagrams Sort each word’s characters to produce equal keys for equal character multisets.
4. Separate keys separatesDifferentCharacterMultisets Create a new list only when the canonical key is absent. Different lengths and characters remain separate.
5. Several buckets groupsStandardExample Accumulate multiple existing and new groups across the complete input.
6. Empty key handlesEmptyStrings Confirm that the empty character sequence is a valid shared key and repeated inputs are preserved.
7. Frequency matters handlesRepeatedLettersAndDifferentLengths Triangulate that keys encode the full character multiset, including counts and length.
8. Case contract case-sensitive letters Keep ordinary character sorting and equality; do not normalize case.

The canonical assertion is important test design: it ignores only the ordering the contract says is irrelevant, while still detecting missing groups, extra groups, or lost duplicate words.