Group Anagrams

What the problem is really asking

Anagrams contain the same letters, just in a different order.

So the real challenge is to find a representation that makes all anagrams look identical.

Intuition

If two words are anagrams, then sorting their characters gives the same result.

For example:

• "eat" -> "aet"
• "tea" -> "aet"

That sorted form can act like a signature.

Brute-force idea

The slow way is to compare every word with every other word and check whether they are anagrams.

That is too expensive.

Optimized approach

Use a hash map:

1. for each word, sort its characters
2. use the sorted string as the key
3. append the original word into that key's group

At the end, every map bucket is one anagram group.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String word : strs) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            groups.computeIfAbsent(key, ignored -> new ArrayList<>()).add(word);
        }

        return new ArrayList<>(groups.values());
    }
}

Dry run

Take ["eat", "tea", "tan", "ate", "nat", "bat"].

• "eat" -> key "aet"
• "tea" -> key "aet"
• "tan" -> key "ant"
• "ate" -> key "aet"
• "nat" -> key "ant"
• "bat" -> key "abt"

So the final groups are:

• ["eat", "tea", "ate"]
• ["tan", "nat"]
• ["bat"]

Common mistakes

1. Grouping by length only

Equal length is not enough. "ab" and "cd" have the same length but are not anagrams.

2. Sorting after grouping

You need the canonical key before deciding which bucket a word belongs to.

3. Forgetting that the original word, not the sorted key, belongs in the answer

The sorted key is only for grouping.

Complexity

Time Complexity: O(n * k log k)

where k is the average word length.

Space Complexity: O(n * k)