Group Anagrams — DSA

Problem

Given an array of strings strs, group together the strings that are anagrams of each other, and return the groups in any order.

Two strings are anagrams if they contain the same characters with the same counts, for example "eat", "tea" and "ate".

Input:  ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]     (any order of groups and of words within groups)

Strings consist of lowercase English letters, and may be empty. The empty string forms its own group.
The key question is how to give all anagrams the same key, so they can be grouped with a hash map.

Examples

Example 1

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

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

Constraints

•1 <= strs.length <= 10^4
•0 <= strs[i].length <= 100

Hints

Hint 1

Sort each string — anagrams produce the same sorted key. Use a HashMap<String, List<String>> keyed by that sorted string.

Hint 2

An alternative key avoids sorting entirely: encode each string's 26-letter frequency COUNT directly as the key (e.g. a delimited count string) — removes the O(k log k) sort per string, dropping to O(k).

Solutions

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);              // anagrams share the same sorted key
        String key = new String(chars);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

Time: O(n * k log k) where k = max string length · Space: O(n*k)