Group Anagrams — Practice

Problem

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

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)