LeetCode 49 · Medium · Arrays & Hashing

Group Anagrams

Given an array of strings strs, group the anagrams together: words made of exactly the same letters, the same number of times. Return the groups in any order.

O(n·k)time
O(n·k)space
26count key

1–10 comma-separated words · letters a–z, 0–8 each · "" is the empty string

strs pointer i walks the words

count letters of s · 26 slots · slot = ord(c) − ord('a')

→

res HashMap · one card per key · key shown as its non-zero slots

public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> res = new HashMap<>(); // key -> words for (String s : strs) { int[] count = new int[26]; for (char c : s.toCharArray()) { count[c - 'a']++; } String key = Arrays.toString(count); res.computeIfAbsent(key, k -> new ArrayList<>()).add(s); } return new ArrayList<>(res.values());}
i
—
s
—
c
—
count
—
res.size()
0

Why it works

  1. Brute force compares every pair of words with an anagram check: O(n²·k) for n words of length up to k.
  2. Give every word a signature that anagrams share and nothing else does. A hash map from signature to list then groups all words in one pass.
  3. Count key vs sorted key. Sorting the characters of each word also works and handles any alphabet, but it costs O(k log k) per word. The 26-count key costs O(k), so the total is O(n·k) time and O(n·k) space for the stored words.
  4. Pitfall: the key must have value equality and be unambiguous. An int[] hashes by identity, so two equal count arrays would land in different buckets; turn it into a String with Arrays.toString. Joining counts into a string without a separator collides: counts (1, 10, 0, …) and (11, 0, 0, …) both become "110…". Put a '#' between counts, as Arrays.toString does with its commas.
  5. Counts matter, not just letters: aab and abb use the same set of letters but land in different groups. The empty string is a valid word too; its key is all zeros.
  6. Follow-up: Unicode or a huge alphabet makes a 26-slot array wrong. Use the sorted-string key, or a Map<Character, Integer> of counts (maps with equal contents are equal keys).