10.4 Group Anagrams

10.4.1 Problem Metadata

10.4.2 Description

Given an array of strings, group the anagrams together. Two strings are anagrams if they contain the same characters with the same multiplicity, regardless of order.

10.4.3 Examples

Input: ["eat","tea","tan","ate","nat","bat"]
Output: [["ate","eat","tea"],["nat","tan"],["bat"]]

10.4.4 Constraints

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase Englc-lish letters

10.4.5 Solution - Hash Signature Map

10.4.5.1 Walkthrough

Anagrams reduce to the same canonical representation once their letters are sorted. Iterate over the strings, sort each one to derive a signature, and use a hash map that stores signature -> lc-list of anagrams. Append every string to its signature bucket and finally return the map values as the grouped result.

10.4.5.2 Analysis

  • Time Complexity: O(n * m log m) to sort each string of length m across n strings
  • Space Complexity: O(n * m) to store all strings inside the hash map

10.4.5.3 Implementation Steps

  1. Initialize Map<String, List<String>> groups.
  2. For every string s, sort its characters to form key.
  3. Append s to groups.get(key), creating the bucket if needed.
  4. Return a lc-list built from the map values.

10.4.5.4 Code - Java

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 signature = new String(chars);
        groups.computeIfAbsent(signature, key -> new ArrayList<>()).add(word);
    }
    return new ArrayList<>(groups.values());
}