Given a sequence of words, print all anagrams together

The problem, simply

You get a list of words. Two words are anagrams when they use exactly the same letters the same number of times, only in a different order, like cat and act.

Put anagrams together. Give back a list of groups, where each group holds words that are anagrams of each other. Keep the groups in the order their first word shows up. Below, N is the number of words and L is the length of the longest word.

A story to remember it

Picture it

Examples

Way 1: the simple way

Take each word that is not in a group yet. Start a new group with it, and pull in every later word that is its anagram.

1. Two words are anagrams if they have the same length and the same letter counts. Count letters up for one word and down for the other. All counts must end at 0.
2. Walk the words. Skip a word that already has a group.
3. Otherwise start a group, then check every later word against it.

import java.util.*;

class Solution {
    private static boolean sameLetters(String a, String b) {
        if (a.length() != b.length()) return false;
        int[] count = new int[26];
        for (char ch : a.toCharArray()) count[ch - 'a']++;
        for (char ch : b.toCharArray()) count[ch - 'a']--;
        for (int c : count) if (c != 0) return false;
        return true;
    }

    public static List<List<String>> groupAnagrams(String[] words) {
        boolean[] used = new boolean[words.length];
        List<List<String>> groups = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (used[i]) continue;
            List<String> group = new ArrayList<>();
            group.add(words[i]);
            for (int j = i + 1; j < words.length; j++) {
                if (!used[j] && sameLetters(words[i], words[j])) {
                    group.add(words[j]);
                    used[j] = true;
                }
            }
            groups.add(group);
        }
        return groups;
    }
}

How long it takes: every pair of words may be compared, and each compare reads up to L letters, O(N^2 * L). Extra room besides the answer: the used marks, O(N).

Way 2: the clever way

Give every word a key: its letters sorted. Anagrams get the same key and other words get different keys. Then file each key in a trie. The node where a key ends remembers which group it belongs to.

1. For each word, sort its letters to make the key.
2. Walk the key into the trie, growing branches that are missing.
3. If the end node has no group yet, start a new group and write its number there.
4. Add the word to the group written at the end node.

import java.util.*;

class Solution {
    private static class Node {
        Node[] next = new Node[26];
        int group = -1;                     // which group ends here, -1 if none yet
    }

    public static List<List<String>> groupAnagrams(String[] words) {
        Node root = new Node();
        List<List<String>> groups = new ArrayList<>();
        for (String w : words) {
            char[] key = w.toCharArray();
            Arrays.sort(key);               // anagrams share the same sorted key
            Node cur = root;
            for (char ch : key) {
                int k = ch - 'a';
                if (cur.next[k] == null) cur.next[k] = new Node();
                cur = cur.next[k];
            }
            if (cur.group == -1) {          // first word with this key
                cur.group = groups.size();
                groups.add(new ArrayList<>());
            }
            groups.get(cur.group).add(w);
        }
        return groups;
    }
}

How long it takes: sorting each word costs O(L log L) and the trie walk costs O(L), so O(N * L log L) in all. Extra room: at most one node per letter, each with 26 slots, O(26 * N * L).

Watch out for

• Comparing only the set of letters. aab and abb have the same letters but different counts. Sorting or counting handles this, a set does not.
• Words of different lengths can never be anagrams. Sorting already keeps them apart, since their keys differ.
• Capital letters, spaces or digits break ch - 'a'. Lowercase first, or use a map for children.

What interviewers ask next

• Why not a HashMap<String, List<String>> with the sorted key? That is the usual answer, and it is as fast. A trie shines when you also need prefix questions about the keys, and it shares the start of similar keys.
• Can you drop the sort? Yes. Build the key from letter counts, like 1a0b1c..., or walk the trie by counts. That makes it O(N * L).
• Find all anagrams of a pattern inside a long text? That is a sliding window with letter counts, not grouping.
• What if words are huge but few? Count letters per word and compare count arrays, since sorting long words costs more.

Remember this

Grown-up words: the sorted tiles are a canonical key, the cabinet of drawers is a trie, the group number on a drawer is data stored at the end of word node, and letter counts as a key are a frequency signature.