Group Anagrams — Hash Map of Canonical Keys

Group Anagrams is a Medium that comes up constantly in onsite loops. It is a great test of whether you can spot the canonicalization pattern: turn each string into a key that all of its anagrams share, then group them with a hash map.

The Problem

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

Example:

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

Constraints typically say up to 10^4 strings, each up to 100 lowercase English letters.

Intuition

The naive approach checks each pair of strings to see if they are anagrams. For each new string, scan the existing groups and join one if a representative is an anagram. That is O(n^2 * k) in the worst case, where n is the number of strings and k is the maximum length. With 10^4 inputs and 100 characters each, that is 10^10 work. It will time out.

The trick is to compute a canonical key for each string. Two strings are anagrams if and only if their canonical keys match. We can use a hash map from key to list, dropping each string into the right bucket in one pass.

Two key representations are common. The sorted string is the shortest code: ''.join(sorted(s)), costing O(k log k) per string. The character count tuple is asymptotically better at O(k) per string. For long strings, prefer the count tuple.

Explanation with Example

Take strs = ["eat","tea","tan","ate","nat","bat"] with the sorted-key version. We compute keys:

• eat becomes aet
• tea becomes aet
• tan becomes ant
• ate becomes aet
• nat becomes ant
• bat becomes abt

Three keys appear: aet, ant, and abt. The map ends up as:

• aet: [eat, tea, ate]
• ant: [tan, nat]
• abt: [bat]

We return the values as a list of lists. The order inside each group reflects the input order, which is acceptable because the problem allows any ordering.

input          sorted key       bucket
"eat"   ----->  "aet"    --+
"tea"   ----->  "aet"    --+--> ["eat","tea","ate"]
"ate"   ----->  "aet"    --+
"tan"   ----->  "ant"    --+
"nat"   ----->  "ant"    --+--> ["tan","nat"]
"bat"   ----->  "abt"    ----> ["bat"]

       groups: { "aet": [...], "ant": [...], "abt": [...] }

sorted key  "eat" -> sort -> "aet"            cost: O(k log k)

count key   "eat" -> [a:1,b:0,...,e:1,...,t:1]  cost: O(k)
                -> tuple( 1,0,...,1,...,1 )

Code

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        counts = [0] * 26
        for ch in s:
            counts[ord(ch) - ord('a')] += 1
        groups[tuple(counts)].append(s)
    return list(groups.values())

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            int[] counts = new int[26];
            for (char c : s.toCharArray()) counts[c - 'a']++;
            StringBuilder key = new StringBuilder();
            for (int v : counts) { key.append(v); key.append('#'); }
            groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;
        for (auto& s : strs) {
            string key(26, '0');
            int counts[26] = {0};
            for (char c : s) counts[c - 'a']++;
            string k;
            for (int v : counts) { k += to_string(v); k += '#'; }
            groups[k].push_back(s);
        }
        vector<vector<string>> result;
        for (auto& p : groups) result.push_back(p.second);
        return result;
    }
};

Edge Cases

• Empty input: return an empty list. The loop runs zero times.
• Empty strings: every empty string is an anagram of every other empty string. Both keys collapse to the empty key, so they end up in one group.
• Very long strings: count keys are faster than sorted keys when k grows, because O(k) beats O(k log k).
• Unicode follow-up: replace the fixed 26 array with a frozen counter, for example tuple(sorted(Counter(s).items())).
• Case sensitivity: by default A and a are different. Normalize if the problem says otherwise.

Complexity Analysis

Let n be the number of strings and k be the maximum length.

• Brute force: O(n^2 * k) time, O(n * k) space.
• Sorted-key hash map: O(n * k log k) time, O(n * k) space for the map and output.
• Count-key hash map: O(n * k) time, O(n * k) space.

The space is dominated by the output itself. A quick recap of these notations is in Big O notation explained.

How to Explain It in an Interview

• Start by recognizing that you need to bucket anagrams, which means equivalent strings need the same key.
• Mention the pairwise comparison baseline and dismiss it as O(n^2 * k).
• Propose the sorted-string key first because it is the shortest code.
• Offer the count-tuple key as an O(n * k) improvement and explain why it matters for long strings.
• Mention the Unicode follow-up so the interviewer sees you have thought beyond the stated constraints.

Related Problems

• Valid Anagram, which is the single-pair version of this question.
• Find All Anagrams in a String, which uses the same count idea inside a sliding window.
• Permutation in String, which is another count-matching variant.

For a refresher on the data structure powering the grouping, see hashing and hash maps.

Wrap up

Group Anagrams is a textbook example of the canonical-key pattern. Pick a representation that collapses equivalent inputs to the same value, then let a hash map do the grouping work in linear time.