#49 Group Anagrams

Mediumsolve on LeetCode ↗

frequently reported atAdobe Walmart Oracle Amazon Apple NVIDIA

the problem

In plain words

Group the strings that are anagrams of each other. Return the groups in any order.

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

out [["bat"],["nat","tan"],["ate","eat","tea"]]

in strs = [""]

out [[""]]

1 ≤ strs.length ≤ 10⁴
0 ≤ strs[i].length ≤ 100
Lowercase English letters

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternGroup by a canonical key Frequency counting

Give every word a canonical key that's identical for all its anagrams — its sorted letters, or its 26 letter counts — and bucket words by key in a HashMap.

solutions

From brute force to optimal

Keep a list of group signatures (sorted letters) and scan it for each word.

sig = sorted(word).
indexOf(sig) in the signature list (a linear scan).
Append to that group or start a new one.

timeO(n·g·k + n·k log k)

Each of n words scans up to g groups comparing k-length signatures, plus sorting each word.

spaceO(n · k)

All words and signatures are stored.

javajava.util.*

1class Solution {2    public List<List<String>> groupAnagrams(String[] strs) {3        List<List<String>> groups = new ArrayList<>();4        List<String> signatures = new ArrayList<>();       // one sorted signature per group5        for (String s : strs) {6            String sig = sorted(s);7            int g = signatures.indexOf(sig);               // linear scan over groups8            if (g < 0) {9                signatures.add(sig);10                groups.add(new ArrayList<>());11                g = groups.size() - 1;12            }13            groups.get(g).add(s);14        }15        return groups;16    }17 18    private String sorted(String s) {19        char[] c = s.toCharArray();20        Arrays.sort(c);21        return new String(c);22    }23}

"eat", "tea" and "ate" all sort to "aet".

For each word: sort its chars → key.
map.computeIfAbsent(key, new list).add(word).
Return the map's values.

timeO(n · k log k)

n words, each sorted in k log k (k = max length).

spaceO(n · k)

Every word and key is stored.

javajava.util.*

1class Solution {2    public List<List<String>> groupAnagrams(String[] strs) {3        Map<String, List<String>> groups = new HashMap<>();4        for (String s : strs) {5            char[] chars = s.toCharArray();6            Arrays.sort(chars);                       // "eat", "tea", "ate" -> "aet"7            String key = new String(chars);8            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);9        }10        return new ArrayList<>(groups.values());11    }12}

Build the 26 counts of each word and use them as the key.

For each word: count letters into int[26].
key = Arrays.toString(count).
Bucket by key.

timeO(n · (k + 26))

Counting is linear in the word; building the key costs 26 more steps.

spaceO(n · k)

The groups plus one fixed-size key per group.

javajava.util.*

1class Solution {2    public List<List<String>> groupAnagrams(String[] strs) {3        Map<String, List<String>> groups = new HashMap<>();4        for (String s : strs) {5            int[] count = new int[26];6            for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;7            String key = Arrays.toString(count); // "[1, 0, 0, 0, 1, ...]": same for all anagrams8            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);9        }10        return new ArrayList<>(groups.values());11    }12}

sim

Dry run

Keys are drawn short (a1 e1 t1); in Java the key is `Arrays.toString(count)`.

loading simulation…

javajava.util.*

1class Solution {2    public List<List<String>> groupAnagrams(String[] strs) {3        Map<String, List<String>> groups = new HashMap<>();4        for (String s : strs) {5            int[] count = new int[26];6            for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;7            String key = Arrays.toString(count); // "[1, 0, 0, 0, 1, ...]": same for all anagrams8            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);9        }10        return new ArrayList<>(groups.values());11    }12}

in the room

How to say it in the interview

talk track

Say: "I need a key that's equal for anagrams and different otherwise" — then offer both keys.
Note the trade-off: sorted keys are simpler; count keys win when words are long.

traps

Using char[] or int[] itself as a HashMap key — arrays use identity hashCode, so equal contents land in different buckets. Convert to a String.
Building the count key by just concatenating digits without separators: counts like [1, 11] and [11, 1] would collide.

what they ask next

Follow-ups

Why is computeIfAbsent nice here?

It creates the list only when the key is new and returns it either way — one line instead of get / null-check / put.

Which key is better in practice?

For short words the sorted key is simpler and often as fast; the count key wins asymptotically when words are long (k ≫ 26).

before you submit

Edge cases to test

An empty string is a word too: [""] → [[""]].
Duplicate words stay as separate entries in the same group.
Count keys need separators: counts [1, 11] and [11, 1] must not collide.

practise next