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 eat and tea.

Put the anagrams next to each other: give back a list of groups, where each group holds words that are anagrams of each other. Here n is the number of words and m is the length of the longest word.

A story to remember it

Picture it

Examples

Way 1: the simple way

Take the first word that has no group yet. Walk through every later word and check: is it an anagram of this one? To check two words, sort both and compare. Mark each word you put in a group so you never use it twice.

1. For each word i that is not used, start a new group with it.
2. For each later word j that is not used, sort both and compare.
3. If they match, add j to the group and mark it used.

import java.util.*;

class Solution {
    private boolean sameLetters(String a, String b) {
        if (a.length() != b.length()) return false;
        char[] x = a.toCharArray(), y = b.toCharArray();
        Arrays.sort(x);
        Arrays.sort(y);
        return Arrays.equals(x, y);
    }

    public List<List<String>> groupAnagrams(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] && sameLetters(words[i], words[j])) {
                    group.add(words[j]);
                    used[j] = true;
                }
            }
            groups.add(group);
        }
        return groups;
    }
}

How long it takes: up to n^2 pairs, and each check sorts two words, so O(n^2 * m log m). Extra room: the groups hold every word, O(n * m).

Way 2: the clever way

Do the sticky note trick. Sort each word's letters once to make its label, the key. Use a map from key to the group of words. Every word goes straight to its bin, so you never compare two words directly.

1. For each word, sort its letters to get the key.
2. If the map has no bin for that key, make an empty one.
3. Add the word to the bin.
4. Give back all the bins.

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] words) {
        // LinkedHashMap keeps the groups in the order they first appear
        Map<String, List<String>> bins = new LinkedHashMap<>();
        for (String w : words) {
            char[] letters = w.toCharArray();
            Arrays.sort(letters);                 // the sticky note
            String key = new String(letters);
            bins.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
        }
        return new ArrayList<>(bins.values());
    }
}

How long it takes: each of the n words is sorted once, O(n * m log m). Extra room: the map stores every word and one key per group, O(n * m).

Way 3: count the letters instead of sorting

If words use only a to z, the label can be the 26 letter counts instead of the sorted word. tea becomes "one a, one e, one t". Counting is a straight walk, so each word costs O(m) instead of O(m log m).

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> bins = new LinkedHashMap<>();
        for (String w : words) {
            int[] count = new int[26];
            for (char c : w.toCharArray()) count[c - 'a']++;
            StringBuilder key = new StringBuilder();
            for (int x : count) key.append('#').append(x);   // '#' keeps 1,12 apart from 11,2
            bins.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(w);
        }
        return new ArrayList<>(bins.values());
    }
}

This takes O(n * m) time (plus 26 per word to build the key) and the same O(n * m) room.

Watch out for

• A plain HashMap gives the groups in a random looking order. Use LinkedHashMap if the order must follow the input.
• Upper and lower case: Tea and eat are only anagrams if you lower case first. Ask the interviewer.
• The empty string is a valid word, and its key is the empty string.
• Do not use the sum of letter codes as a key. ad and bc have the same sum but are not anagrams.

What interviewers ask next

• Is s an anagram of t? Count letters of s up and letters of t down in one 26 slot table, then check every slot is 0.
• Find all places in a long text where an anagram of p starts. Slide a window of length p.length() and keep a 26 slot count.
• What about Unicode words? Sorting still works. For counts, use a HashMap<Character, Integer> and build a key from the sorted entries.
• Could you multiply one prime per letter as the key? Yes in theory, every group gets a unique product, but long words overflow long. Mention it, then prefer the count key.
• Very many words that do not fit in memory? Write key, word pairs to disk, sort them by key, and read groups off in order.

Remember this

Grown-up words: the sticky note is a canonical form, the bins are a hash map from key to list, and the letter count label is a frequency signature.