Group Anagrams

Approach Summary

Sort each string to get its canonical form. Group strings with the same sorted form using a hash map.

Full Solution & Approach

Anagrams share the same character multiset, so they share the same sorted-string form. Group by that normalized key: for each string, build key = sorted(s) joined, and append the string to the bucket for that key in a dictionary. Strings that are anagrams of each other produce identical keys and land in the same bucket. Return the buckets as a list. Complexity is O(n · k log k), where n is the number of strings and k the maximum length, dominated by sorting each string. The alternative count-array-as-tuple approach buckets by a 26-length frequency tuple and runs in O(n · k), avoiding the sort — it is the more efficient of the two and worth mentioning in an interview. Grouping by a canonical form is the core idea to take away.

Each of n strings of length k is sorted in O(k log k) — O(n · k log k) total. The map holds every string, so O(n · k) space.

Solution Code

Solution

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        groups[''.join(sorted(s))].append(s)
    return list(groups.values())

function groupAnagrams(strs) {
  const groups = new Map();
  for (const s of strs) {
    const key = [...s].sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(s);
  }
  return [...groups.values()];
}

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

vector<vector<string>> groupAnagrams(const vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (const string& s : strs) {
        string key = s;
        sort(key.begin(), key.end());
        groups[key].push_back(s);
    }
    vector<vector<string>> res;
    for (auto& [k, v] : groups) res.push_back(v);
    return res;
}

Edge Cases to Watch

Empty strings — all map to the same key and group together
Single characters — grouped by the character itself
Case sensitivity — the key is case-sensitive, keeping "a" and "A" separate per problem constraints
A single group for identical strings

How to Recognize This Pattern

Group strings that are anagrams
Canonical key per anagram group

Complexity Analysis

Time Complexity

O(n · k log k)

Space Complexity

O(n · k)