Free lesson · DSA Mastery - Interview Prep, End to End

Group Anagrams

Medium6 min readdsahash-tables

Group Anagrams

Group Anagrams is the classic bucket-by-canonical-form problem. The question is how to recognize that two strings are anagrams and group them together. The clean solution: compute a canonical key for each string (sorted letters, or character-count signature), and use a hash map from key → list of strings.

The problem demonstrates how hash tables enable elegant grouping operations. The trick is choosing the right key.

The Problem

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

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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

Example 2:

Input:  strs = [""]
Output: [[""]]

Example 3:

Input:  strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

Approach

Two clean approaches for computing the canonical key.

Approach 1: Sorted String Key

Sort the characters of each string. Anagrams have the same sorted form.

char[] arr = s.toCharArray();
Arrays.sort(arr);
String key = new String(arr);

O(k log k) per string where k is its length. Easy to implement.

Approach 2: Character-Count Key

Build a 26-element count array. Use a deterministic string representation (e.g., "#1#0#2#...") as the key.

int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
StringBuilder sb = new StringBuilder();
for (int c : count) sb.append('#').append(c);
String key = sb.toString();

O(k + 26) per string. Slightly faster than sorting for long strings.

For most inputs, the sort approach is simple and fast enough. Use it unless the strings are very long (say, k > 50).

graph TD
    A["For each str in strs"] --> B["key = canonical(str)"]
    B --> C["Add str to groups[key]"]
    C --> D{"More?"}
    D -->|Yes| A
    D -->|No| E["Return groups.values()"]
    
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram shows the bucket-by-canonical-form approach. For each string, we compute a canonical key - either the sorted characters or a character-count signature. We group strings by this key in a hash map. At the end, the values of the map are the anagram groups.

Code Implementation

Sorted String Key (Recommended for Interview)

public static 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());
}

// Usage:
// String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
// System.out.println(groupAnagrams(input));
// Output: [[eat, tea, ate], [tan, nat], [bat]]  (order may vary)

This Java code implements Group Anagrams using sorted strings as keys. For each string, we sort its characters and use the sorted form as a hash key. We group strings by key in a HashMap of String to List of String. The final result is the collection of value lists.

computeIfAbsent is a clean idiom for "create list if needed, then append." It's equivalent to:

if (!groups.containsKey(key)) groups.put(key, new ArrayList<>());
groups.get(key).add(s);

Character-Count Key (Optimization for Long Strings)

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

The '#' separator prevents counts from running together (so "1, 12" and "11, 2" produce different keys).

Walkthrough

Trace the sorted-key approach on strs = ["eat", "tea", "tan", "ate", "nat", "bat"].

"eat": sorted = "aet". groups = {"aet": [eat]}.
"tea": sorted = "aet". groups["aet"] adds "tea". groups = {"aet": [eat, tea]}.
"tan": sorted = "ant". groups = {"aet": [eat, tea], "ant": [tan]}.
"ate": sorted = "aet". groups["aet"] adds "ate". groups = {"aet": [eat, tea, ate], "ant": [tan]}.
"nat": sorted = "ant". groups["ant"] adds "nat". groups = {"aet": [eat, tea, ate], "ant": [tan, nat]}.
"bat": sorted = "abt". groups = {"aet": [eat, tea, ate], "ant": [tan, nat], "abt": [bat]}.

Return values: [[eat, tea, ate], [tan, nat], [bat]].

Result: [[eat, tea, ate], [tan, nat], [bat]] (order may vary).

Complexity Analysis

Where n = number of strings, k = max string length.

Why Sort Is O(n · k log k)

For each of n strings, sorting takes O(k log k). Building the key as a String is O(k). Hash operations are O(k) (hash and compare). Total: O(n · k log k).

Why Count Is O(n · k)

For each string, counting is O(k). Building the key is O(26). Hash operations are O(26 + k) for the key length. Total: O(n · k).

For very long strings, count is faster. For short strings, the constant factors of sort are negligible. Either is fine in most interviews.

Why Space Is O(n · k)

Storing all strings in the result (or in the hash map) is unavoidable - that's the output. The keys add at most O(n · k) more.

Variations & Follow-ups

What if you wanted only the group sizes, not the strings themselves?

Use Map<String, Integer> and increment counts. Return the values (sorted descending or as-is).

What if you needed to return groups in a specific order (e.g., by group size)?

Sort the values list before returning:

List<List<String>> result = new ArrayList<>(groups.values());
result.sort((a, b) -> b.size() - a.size());
return result;

What about Unicode characters?

The sort approach still works (Unicode strings sort like any other).

The count approach needs adjustment - use HashMap<Character, Integer> for the count, and construct the key carefully.

What if there were billions of strings?

Hashing scales well, but in-memory hash maps may not. Use MapReduce or distributed key-value stores. Sort approach can use external sort for distributed grouping.

What about anagrams across different scripts (e.g., Latin + Cyrillic)?

Anagrams are usually defined within a single character set. Cross-script anagrams are nonsensical for most applications.

What if you needed to detect "subsequence anagrams" (one string's letters are a subset)?

Different problem - that's a multiset containment check, not an equality check.

What about edge cases?

• Empty input array: Returns empty list. (Constraint says length >= 1.)
• Single empty string: Key is "", groups = {"": [""]}. Returns [[""]].
• All identical strings: All have the same key. Returns one group with all duplicates.
• All distinct (no anagrams): Each string in its own group. Returns n groups of 1.
• Mix of capitalizations: Problem says lowercase only. For mixed, lowercase first.

Common Interview Pitfalls

• Using Arrays.sort on int[] instead of char[]. Different methods, different inputs. Use Arrays.sort(charArray) for chars.
• Not separating count digits in the count-key approach. Without separators like '#', the count [1, 12, 0, ...] and [11, 2, 0, ...] produce the same key. Use a delimiter.
• Using the unsorted string as the key. That defeats the purpose - anagrams need to hash to the same bucket.
• Reaching for sorting on the entire array. You're sorting individual strings, not the array.
• Worrying about hash collisions. Java's HashMap handles collisions internally. Two strings with the same sorted form will share a bucket (and that's what we want); strings with different sorted forms have different keys (even if they happen to hash to the same bucket, equality is checked).

Why This Problem Matters

Group Anagrams is the canonical bucket by canonical form problem. The pattern of "compute a key that identifies the equivalence class, group by key" appears in many problems:

• Partition by some property in data analysis.
• Deduplication when items are equal under a non-trivial equivalence.
• Find connected components in equivalence graphs (Union-Find is another way).
• Counting distinct equivalence classes in combinatorics.

The choice of canonical form is the creative part:

• Anagrams: sorted letters or character counts.
• Cyclic permutations: smallest rotation (Booth's algorithm) or s + s membership.
• Reflections: smallest of {s, reverse(s)}.
• Affine equivalence: quotient by the equivalence relation.

If you can identify the canonical form, the grouping algorithm follows mechanically. Group Anagrams makes the pattern explicit.

The next topic, Group Shifted Strings, applies the same technique with a more interesting canonical form: the "shift profile" of a string under Caesar shifts.

Back to DSA Mastery - Interview Prep, End to End