4.Group Anagrams

MediumBlind 75Arrays & Hashing · 4/9

Problem

Given an array of strings strs, group the strings that are anagrams of each other and return the groups. The groups, and the strings inside each group, may be returned in any order.

Two strings are anagrams when they contain exactly the same letters with the same counts, e.g. "eat", "tea" and "ate".

Examples

Input:  strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
Explanation: "eat", "tea", "ate" share letters {a,e,t}; "tan", "nat" share {a,n,t}; "bat" is alone.

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

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

Constraints

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

💡 Key Insight

Give every string a canonical key that is identical for all its anagrams and different for everything else, then bucket strings by key in a HashMap<String, List<String>>. Two good keys exist: the sorted string ("eat" → "aet"), or the 26-letter frequency signature ("eat" → 1#0#0#0#1#...#1#...). The frequency key avoids the per-string sort.

Brute Force

TimeO(n² · k)SpaceO(n)

Intuition

Take the first ungrouped string, start a new group, then scan all remaining ungrouped strings and pull in those that are anagrams of it (checked with a 26-letter count comparison). Repeat until every string is grouped.

Algorithm

Keep a boolean[] used.
For each i not yet used: start group = [strs[i]], mark used[i].
For each j > i not used: if isAnagram(strs[i], strs[j]), add it to group and mark used[j].
Append group to the result.

Visualization

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

i=0 eat: tea ✓, tan ✗, ate ✓, nat ✗, bat ✗ → [eat, tea, ate]
i=2 tan: nat ✓, bat ✗                       → [tan, nat]
i=5 bat:                                     → [bat]

Code

java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int n = strs.length;
        boolean[] used = new boolean[n];
        List<List<String>> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
            List<String> group = new ArrayList<>();
            group.add(strs[i]);
            used[i] = true;
            for (int j = i + 1; j < n; j++) {
                if (!used[j] && isAnagram(strs[i], strs[j])) {
                    group.add(strs[j]);
                    used[j] = true;
                }
            }
            result.add(group);
        }
        return result;
    }

    private boolean isAnagram(String a, String b) {
        if (a.length() != b.length()) {
            return false;
        }
        int[] count = new int[26];
        for (int k = 0; k < a.length(); k++) {
            count[a.charAt(k) - 'a']++;
            count[b.charAt(k) - 'a']--;
        }
        for (int c : count) {
            if (c != 0) {
                return false;
            }
        }
        return true;
    }
}

Complexity

Time: O(n² · k) — up to n² pair comparisons, each O(k) where k is the max string length.
Space: O(n) — the used array (output not counted).

Sorted String Key

TimeO(n · k log k)SpaceO(n · k)

Intuition

All anagrams sort to the same string: "eat", "tea", "ate" all become "aet". Use that sorted string as a map key, and every anagram lands in the same bucket in a single pass.

Algorithm

Create Map<String, List<String>> groups.
For each s: sort its characters into key, then groups.computeIfAbsent(key, ...).add(s).
Return new ArrayList<>(groups.values()).

Visualization

eat → aet ┐
tea → aet ├─ "aet": [eat, tea, ate]
ate → aet ┘
tan → ant ┐
nat → ant ┴─ "ant": [tan, nat]
bat → abt ── "abt": [bat]

Code

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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); // all anagrams share this sorted form
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

Complexity

Time: O(n · k log k) — each of the n strings is sorted in O(k log k).
Space: O(n · k) — the map stores every string plus its key.

Character Count KeyOptimal

TimeO(n · k)SpaceO(n · k)

Intuition

Sorting each string costs O(k log k), but counting its letters costs only O(k). The 26 counts uniquely identify an anagram class, so turn them into a string key such as "1#0#0#0#1#...#1#...". A separator is required so that counts like 1,11 and 11,1 produce different keys.

Algorithm

Create Map<String, List<String>> groups.
For each s:
- Count its letters into int[26] count.
- Build key by joining the 26 counts with #.
- Add s to groups[key].
Return the map's values.

Dry Run

flowchart LR
    A["eat"] --> K1["a1 e1 t1"]
    B["tea"] --> K1
    C["ate"] --> K1
    D["tan"] --> K2["a1 n1 t1"]
    E["nat"] --> K2
    F["bat"] --> K3["a1 b1 t1"]
    K1 --> G1["[eat, tea, ate]"]
    K2 --> G2["[tan, nat]"]
    K3 --> G3["[bat]"]

Code

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (int i = 0; i < s.length(); i++) {
                count[s.charAt(i) - 'a']++;
            }
            // Build a key like "1#0#0#...": the '#' keeps multi-digit counts unambiguous
            StringBuilder key = new StringBuilder();
            for (int c : count) {
                key.append(c).append('#');
            }
            groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

Complexity

Time: O(n · k) — counting is O(k) per string and building the key is O(26).
Space: O(n · k) — the stored strings plus one O(26) key per group.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n² · k)	O(n)
Sorted String Key	O(n · k log k)	O(n · k)
Character Count Key	O(n · k)	O(n · k)

Common Pitfalls

Using int[] directly as a map key — arrays use identity hashCode/equals, so no two strings ever share a bucket. Convert to a String (or Arrays.toString).
Building the count key without separators — counts [1, 11] and [11, 1] would both become "111".
Using chars.toString() instead of new String(chars) — it returns something like [C@1b6d3586, not the characters.
Forgetting the empty string: "" is a valid input and must form its own group.