Group Anagrams

Master this topic with zero to advance depth.

Group Anagrams

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.

Visual Representation

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

1. Sort each string to create a 'key':
   "eat" -> "aet"
   "tea" -> "aet"
   "tan" -> "ant"
   ...

2. Group by key in a Hash Map:
   "aet" -> ["eat", "tea", "ate"]
   "ant" -> ["tan", "nat"]
   "abt" -> ["bat"]

Medium

Examples

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
"eat", "tea", and "ate" are anagrams. "tan" and "nat" are anagrams. "bat" is alone.

Approach 1

Level I: Brute Force (Compare All Pairs)

Intuition

Compare every string with every other string to check if they are anagrams. We use a used boolean array to keep track of strings that have already been grouped. This is the simplest baseline approach but inefficient for large inputs.

⏱ O(N² * K log K) where N is the number of strings and K is the average length of strings (due to sorting for comparison).💾 O(N * K) to store the result.

Detailed Dry Run

String A	String B	Sorted(A)	Sorted(B)	Is Anagram?
"eat"	"tea"	"aet"	"aet"	Yes
"eat"	"tan"	"aet"	"ant"	No
"tan"	"nat"	"ant"	"ant"	Yes

java

import java.util.*;

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

    private static boolean areAnagrams(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        return Arrays.equals(c1, c2);
    }

    public static void main(String[] args) {
        String[] strs = {"eat","tea","tan","ate","nat","bat"};
        System.out.println(groupAnagrams(strs));
    }
}

Approach 2

Level II: Better Solution (HashMap with Sorted String Key)

Intuition

Instead of nested loops, we use a Hash Map. Since all anagrams share the same sorted version, we sort each string and use it as a key. All strings that result in the same sorted string are added to the same list.

⏱ O(N * K log K) where N is the number of strings and K is the maximum length of a string.💾 O(N * K) to store the Hash Map.

Detailed Dry Run

Input String	Sorted Key	Action
"eat"	"aet"	Map["aet"] = ["eat"]
"tea"	"aet"	Map["aet"] = ["eat", "tea"]
"tan"	"ant"	Map["ant"] = ["tan"]

java

import java.util.*;

public class Main {
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String key = String.valueOf(ca);
            if (!map.containsKey(key)) map.put(key, new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) {
        String[] strs = {"eat","tea","tan","ate","nat","bat"};
        System.out.println(groupAnagrams(strs));
    }
}

Approach 3

Level III: Optimal Solution (Frequency Bucket Key)

Intuition

Instead of sorting each string ( $O(K \log K)$ ), we can use the character frequencies (26 characters) as the Hash Map key. This reduces the transformation time to linear $O(K)$ . We represent the count array as a string or tuple to use as a key.

⏱ O(N * K) where N is the number of strings and K is the maximum length of a string.💾 O(N * K) to store the Hash Map and count strings.

Detailed Dry Run

Bucket Count Key

Char	Frequency Count Array
eat	[1, 0, 0, 0, 1, ..., 1, ...] (a:1, e:1, t:1)
tea	[1, 0, 0, 0, 1, ..., 1, ...] (same signature)

Logic: key = "#1#0#0...#1". Anagrams share the same key without ever sorting.

java

import java.util.*;

public class Main {
    public static List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<>();
        Map<String, List<String>> map = 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 i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }
            String key = sb.toString();
            if (!map.containsKey(key)) map.put(key, new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) {
        String[] strs = {"eat","tea","tan","ate","nat","bat"};
        System.out.println(groupAnagrams(strs));
    }
}

← Previous QuestionContains Duplicate

Next Question →Longest Consecutive Sequence

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.