49. Group Anagrams

Group Anagrams is the problem that teaches you to design a hash key instead of just using one. The trick is finding a fingerprint that two anagrams share and nothing else does — a classic move in the arrays and hashing pattern. Once you see it here, a lot of “group things that are secretly equal” problems look the same.

The problem

You’re handed a list of strings and asked to bucket them so that words made of the same letters (in any order) land together. Return the groups in any order. (Full statement on LeetCode.)

So ["eat", "tea", "ate", "bat", "tab"] becomes [["eat", "tea", "ate"], ["bat", "tab"]]. The order inside a group and between groups doesn’t matter.

Intuition: give every anagram the same fingerprint

Two words are anagrams exactly when they have the same multiset of letters. So the whole problem reduces to one question: what value can I compute from a word that is identical for anagrams and different for everything else? Feed that value into a hash map, and grouping is just “drop each word in the bucket its key points to.”

There are two natural fingerprints:

• Sort the letters. "eat" and "tea" both sort to "aet". Simple, and it works for any alphabet — but sorting each word of length $k$ costs $O(k \log k)$.
• Count the letters. Since the input is lowercase a–z, a 26-slot tally like [a:1, e:1, t:1] is a fingerprint too, and building it is $O(k)$ — no sort. Turn that array into a string and it becomes a map key.

Both are correct. The count-array key is the one interviewers are usually fishing for, because it drops the $\log k$ factor.

Solution

Start with the sorted-key version, since it reads like the intuition — one line to make the key:

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);              // "tea" -> "aet"
            String key = new String(chars);  // anagrams collapse to one key
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

The count-array version swaps the sort for a frequency tally. For each word, tally its letters into int[26], then serialize that array as the key — anagrams produce the identical tally, so they collapse to the same bucket:

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) count[c - 'a']++;
            // Arrays.toString gives a stable, unique text form of the tally
            String key = Arrays.toString(count);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

One caveat on the key: don’t hand the raw int[] to the map. Arrays use identity hashing in Java, so two equal tallies would land in different buckets. Arrays.toString(count) (or a delimited string built by hand) gives a value-based key that hashes correctly.

Complexity

Let $n$ be the number of words and $k$ the max word length.

Approach	Time	Space
Sorted key	$O(n(k \log(k{+}1) + 1))$	$O(n(k{+}1))$
Count-array key	$O(n(k{+}1))$	$O(n \log(k{+}1) + n + k)$

(The $+1$ terms keep the bounds honest for empty strings: even with $k = 0$ you still do $\Theta(n)$ work touching each of the $n$ words.)

The space differs because of what each key is. A sorted key is a $k$-character string, so the map holds $O(n \cdot k)$ characters of keys. A count-array key is smaller but not free: Arrays.toString of a 26-slot tally produces a string whose length grows with the digit width of the counts ($O(\log(k{+}1))$ per word, so $O(n \log(k{+}1))$ across the map), plus $O(n)$ for the map and list references and an $O(k)$ scratch buffer from toCharArray. Either way the map values are just references to the original input strings, not copies. The count-array key is also asymptotically faster in time — it drops the $\log k$ sorting factor — though for very short strings the serialization overhead can make it a wash or slightly slower.

In an interview

Say the key idea out loud before any code: “anagrams share a canonical form, so I’ll hash each word by that form and group by bucket.” Offer the sorted key first because it’s obviously correct, then upgrade to the count-array key when they ask for better than $O(k \log k)$ per word — showing you can trade a sort for a counting pass is the point being graded.

The trap to name is the map key itself: reaching for int[] as a key silently breaks grouping because arrays hash by identity, not contents. Mentioning that unprompted signals you actually know how Java’s HashMap compares keys.

This canonical-key idea is exactly how you’d check a single pair in Valid Anagram — Group Anagrams just runs that comparison across a whole list via a map. The same letter-frequency counting also drives Top K Frequent Elements. The arrays and hashing hub collects the rest of the family.

References

• LeetCode 49 — Group Anagrams