46. Group Anagrams

Anagrams are permutations of the same letters — sort their characters and they collide to the same canonical string. Group by that key.

Approach

1. Build a dict groups: sorted_key -> list[str].
2. For each s, compute key = "".join(sorted(s)) and append.
3. Return list(groups.values()).

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

Two strings are anagrams iff they have the same letter frequencies. Encoding each string as a length-26 count tuple gives a canonical key in O(k) time, beating the sort-based approach's O(k log k).

Why count tuples are canonical

Two strings s and t are anagrams iff Counter(s) == Counter(t). Since the alphabet is fixed (26 lowercase letters), the counter is just a length-26 vector. A tuple of those counts is hashable and equality-comparable in O(1) per dict op — perfect dict key.

Steps

1. Initialise groups = {}.
2. For each s in strs:
   • Build count = [0] * 26.
   • For each character c in s, increment count[ord(c) - ord('a')].
   • Use tuple(count) as the key in groups and append s to that bucket.
3. Return list(groups.values()).

Walk-through

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

Final groups: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]. ✓

Why this beats the sorted-key approach

• Sorted-key: sorted(s) is O(k log k). For n strings: O(n · k log k).
• Count-key: building each tuple is O(k). Total: O(n · k). The log k factor disappears.

For typical interview constraints (small k) the difference is negligible, but for very large k it matters.

Edge cases

• Empty string: counts are all zero → goes into a single bucket of empties.
• Duplicate strings: end up in the same bucket (which is correct — "abc" and "abc" are anagrams of each other).

Complexity

• Time: O(n · k) — one linear pass over each string.
• Space: O(n · k) — to store all the strings and tuples.