Group Strings That Are Anagrams of Each Other

Medium15–20 min

Topics

StringHash TableSorting

Companies

AmazonGoogleUberFacebook

Given an array of strings strs, group the anagrams together. Two strings are anagrams of each other if one can be rearranged into the other using every letter exactly once. You can return the groups — and the strings inside each group — in any order. Comparing every pair of strings directly is expensive. The key insight: two strings are anagrams exactly when their letters, sorted, produce the same string — so sorting each string's letters gives a canonical "key" that's identical for every member of a group. Scanning a list of seen keys works but is quadratic; storing groups in a hash map keyed by that sorted string collapses lookups to O(1), leaving sorting as the only real cost.

Test Case 1:

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

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

Explanation:Groups can be returned in any order, and the strings within each group can be in any order too.

Test Case 2:

Input:strs = [""]

Output:[[""]]

Explanation:A single empty string forms its own group of one.

Test Case 3:

Input:strs = ["a"]

Output:[["a"]]

Explanation:A single one-letter string forms its own group of one.

Constraints

◆1 ≤ strs.length ≤ 10⁴
◆0 ≤ strs[i].length ≤ 100
◆strs[i] consists of lowercase English letters

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

strs (comma-separated words) — 2-6 lowercase words

1	class Solution {
2	public String[][] groupAnagrams(String[] strs) {
3	Map<String, List<String>> map = new HashMap<>();
4	for (String str : strs) {
5	char[] arr = str.toCharArray();
6	Arrays.sort(arr);
7	String key = new String(arr);
8	map.putIfAbsent(key, new ArrayList<>());
9	map.get(key).add(str);
10	}
11	String[][] result = new String[map.size()][];
12	int i = 0;
13	for (List<String> group : map.values()) {
14	result[i++] = group.toArray(new String[0]);
15	}
16	return result;
17	}
18	}
19

Array

eat

tea

tan

ate

↑i

HashMap

empty

Variables

streat

keyaet

key = sort("eat")

= "aet"

CALCULATE

strs[0] = "eat" — sort its letters to get key "aet".

Step 1 / 9

Approach & Solutions

Brute Force — Sort Each String, Linear Search for Its Group

Brute

Sort the letters of each string to get a canonical "key" — two strings are anagrams exactly when their sorted forms are identical. Keep a running list of keys seen so far; for every new string, scan that list from the start looking for a match. Found it → join that group. Not found → start a new group. The linear scan over already-seen keys is what makes this quadratic overall.

TimeO(n² · k log k)

SpaceO(n · k)

Java

Try it out

class Solution {
    public String[][] groupAnagrams(String[] strs) {
        List<String> keys = new ArrayList<>();
        List<List<String>> groups = new ArrayList<>();
        for (String str : strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            int index = keys.indexOf(key);
            if (index == -1) {
                keys.add(key);
                List<String> newGroup = new ArrayList<>();
                newGroup.add(str);
                groups.add(newGroup);
            } else {
                groups.get(index).add(str);
            }
        }
        String[][] result = new String[groups.size()][];
        for (int i = 0; i < groups.size(); i++) {
            result[i] = groups.get(i).toArray(new String[0]);
        }
        return result;
    }
}

Optimal — Group by Sorted-Character Key (Hash Map)

Optimal

Same canonical key idea, but instead of scanning a list of keys, store groups in a hash map keyed by that sorted string. Looking up or creating a group is now O(1) — no scanning required — so the total time collapses to just the cost of sorting each string's letters.

TimeO(n · k log k)