☕ DSA Java Articles

Topics › Strings › Medium String Problems

Group Words by Anagrams

Medium TUF ID 559 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of words. Group together the words that are anagrams of each other, meaning one can be rearranged into the other using every letter exactly as many times. Return the list of groups.

LeetCode accepts the groups in any order. To make the output deterministic (and testable), the methods here list groups in the order their first word appears in the input, and keep words inside a group in input order. Duplicate words stay as separate entries.

Constraints: 1 ≤ n ≤ 10^4 words, each of length 0 ≤ k ≤ 100, lowercase English letters only.

Example 1

words  = ["eat", "tea", "tan", "ate", "nat", "bat"]
answer = [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
// "eat", "tea", "ate" all use one a, one e, one t

Example 2

words  = ["", "b", ""]
answer = [["", ""], ["b"]]
// two empty words are anagrams of each other; "b" stands alone

The key idea: a canonical signature

Being anagrams is an equivalence relation: every word is an anagram of itself, the relation is symmetric, and if x ~ y and y ~ z then x ~ z. So the words split cleanly into disjoint groups, and the question is only how to find which group each word belongs to.

Comparing words pairwise works but is slow. The faster idea is to compute, for each word, a signature that is identical for all anagrams and different for non-anagrams. Then grouping becomes “put each word in the bucket named by its signature”, a single pass with a hash map. The approaches below differ only in which signature they use.

Approach 1: Brute force, compare against every other word

Intuition. Walk through the words. The first word that has not been placed yet starts a new group; then scan every later unplaced word and pull in the ones that are anagrams of it. Because the relation is transitive, comparing against the group’s first word is enough: anything that is an anagram of another group member is also an anagram of the first.

The pairwise test is the Valid Anagram check: equal lengths and equal letter counts, using one array of 26 counters that the first word increments and the second decrements.

Algorithm.

  1. Keep a used flag per word.
  2. For each i not yet used: start a group with words[i], mark it used.
  3. For each later j not yet used: if isAnagram(words[i], words[j]), add it to the group and mark it used.
  4. Append the group to the answer.
static List<List<String>> bruteForce(String[] words) {
    int n = words.length;
    boolean[] used = new boolean[n];
    List<List<String>> groups = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        List<String> group = new ArrayList<>();
        group.add(words[i]);
        used[i] = true;
        for (int j = i + 1; j < n; j++) {
            if (!used[j] && isAnagram(words[i], words[j])) {
                group.add(words[j]);
                used[j] = true;
            }
        }
        groups.add(group);
    }
    return groups;
}

/** Two lowercase words are anagrams when every letter occurs equally often in both. */
static boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) return false;
    int[] count = new int[26];
    for (int i = 0; i < a.length(); i++) {
        count[a.charAt(i) - 'a']++;
        count[b.charAt(i) - 'a']--;
    }
    for (int c : count) if (c != 0) return false;
    return true;
}

Complexity. Time O(n^2 · k): up to n(n-1)/2 comparisons, each O(k + 26). Space O(n) for the flags, plus the output.

With n = 10^4 that is about 5 × 10^7 comparisons of up to 100 letters each, which is too slow. The waste is that we compare a word with every group’s first word, even though a single fingerprint of the word would tell us its group immediately.

Approach 2: Better, the sorted word as the key

Intuition. Sorting the letters of a word erases their order and keeps exactly their counts. So two words are anagrams if and only if their sorted forms are equal: "eat", "tea" and "ate" all sort to "aet". Use the sorted string as a hash-map key and append each word to the list stored under its key.

A LinkedHashMap remembers the order in which keys were first inserted, which gives us the first-appearance order of groups for free. A plain HashMap is fine if order does not matter.

Algorithm.

  1. For each word, sort its characters to get key.
  2. Append the word to groups[key], creating the list if needed.
  3. Return the map’s values as a list.
static List<List<String>> better(String[] words) {
    Map<String, List<String>> groups = new LinkedHashMap<>();    // LinkedHashMap keeps first-appearance order
    for (String w : words) {
        char[] letters = w.toCharArray();
        Arrays.sort(letters);
        String key = new String(letters);
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
    }
    return new ArrayList<>(groups.values());
}

Complexity. Time O(n · k log k): one sort per word. Hashing a key of length k costs O(k), which is dominated by the sort. Space O(n · k) for the keys and the output.

Approach 3: Optimal, letter counts as the key

Intuition. Sorting does more work than necessary. We only need the multiset of letters, and with a 26-letter alphabet that is just 26 counts, which one pass over the word computes. Turn the count array into a string so it can serve as a hash-map key.

The counts must be separated in the key. Without a separator, a word with counts a = 1, b = 11 and one with a = 11, b = 1 would both produce "111...". Writing "1#11#" versus "11#1#" keeps them apart.

Algorithm.

  1. For each word, count each letter into count[26].
  2. Build key as count[0] + "#" + count[1] + "#" + ... + count[25] + "#".
  3. Append the word to groups[key].
  4. Return the map’s values.
static List<List<String>> optimal(String[] words) {
    Map<String, List<String>> groups = new LinkedHashMap<>();
    for (String w : words) {
        int[] count = new int[26];
        for (int i = 0; i < w.length(); i++) count[w.charAt(i) - 'a']++;
        StringBuilder key = new StringBuilder();
        for (int c : count) key.append(c).append('#');         // '#' keeps counts 1,11 apart from 11,1
        groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(w);
    }
    return new ArrayList<>(groups.values());
}

Dry run on ["eat", "tea", "tan", "ate", "nat", "bat"]. The keys are written in short form, listing only non-zero counts, and groups are labelled by their sorted letters for readability:

word key (non-zero counts) groups after this word
eat a1 e1 t1 {aet: [eat]}
tea a1 e1 t1 {aet: [eat, tea]}
tan a1 n1 t1 {aet: [eat, tea], ant: [tan]}
ate a1 e1 t1 {aet: [eat, tea, ate], ant: [tan]}
nat a1 n1 t1 {aet: [eat, tea, ate], ant: [tan, nat]}
bat a1 b1 t1 {…, abt: [bat]}

Complexity. Time O(n · (k + 26)), which is O(n · k) for a fixed alphabet: one counting pass and a 26-entry key per word. Space O(n · k) for the output and O(26 n) for the keys.

For short words (k around 5) the sorted key is often just as fast in practice, because building a 26-number string costs more than sorting five characters. The counting key wins clearly when words are long. Both are accepted; the counting key is the asymptotically better answer and the one to present as optimal.

Edge cases and pitfalls