Group Anagrams

medium
Arrays & HashingStringHash TableSorting

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An anagram is a word formed by rearranging the letters of another word, using all the original letters exactly once.

Examples

Example 1

  • Input: strs = ["eat","tea","tan","ate","nat","bat"]
  • Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
  • Explanation: Strings that are anagrams of each other are grouped together.

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.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Sort Each String as Key

Intuition

Two strings are anagrams if and only if their sorted forms are identical. We can use the sorted version of each string as a hash map key. For every string in the input, sort it, then add the original string to the list associated with that sorted key. Finally, collect all the lists from the map.

Algorithm

  1. Create a hash map where keys are sorted strings and values are lists of original strings.
  2. For each string in the input, sort its characters to produce a key.
  3. Add the original string to the list mapped to that key.
  4. Return all values from the hash map as the result.
TimeO(n * k log k) where n is the number of strings and k is the maximum string lengthSpaceO(n * k)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;

        for (const string& s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            groups[key].push_back(s);
        }

        vector<vector<string>> result;
        for (auto& [key, group] : groups) {
            result.push_back(group);
        }
        return result;
    }
};
Java 21
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);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

        return new ArrayList<>(groups.values());
    }
}
Python 3.12
from collections import defaultdict


def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)

    for s in strs:
        key = "".join(sorted(s))
        groups[key].append(s)

    return list(groups.values())
Go 1.26
import "sort"

func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)

    for _, s := range strs {
        bytes := []byte(s)
        sort.Slice(bytes, func(i, j int) bool { return bytes[i] < bytes[j] })
        key := string(bytes)
        groups[key] = append(groups[key], s)
    }

    result := make([][]string, 0, len(groups))
    for _, group := range groups {
        result = append(result, group)
    }
    return result
}
Approach 2

Character Count as Key

Intuition

Instead of sorting each string, we can build a frequency count of its characters and use that count as the key. For lowercase English letters, we create an array of 26 integers and convert it to a string representation. This avoids the O(k log k) sorting cost per string, replacing it with O(k). Two strings are anagrams if and only if their character frequency arrays are identical.

Algorithm

  1. Create a hash map where keys are character frequency representations and values are lists of strings.
  2. For each string, build an array of 26 counts representing the frequency of each letter.
  3. Convert the count array to a string key (e.g., "1#0#0#...#0#" for "a").
  4. Add the original string to the list mapped to that key.
  5. Return all values from the hash map.
TimeO(n * k) where n is the number of strings and k is the maximum string lengthSpaceO(n * k)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;

        for (const string& s : strs) {
            int count[26] = {0};
            for (char c : s) {
                count[c - 'a']++;
            }

            string key;
            for (int i = 0; i < 26; i++) {
                key += to_string(count[i]);
                key += '#';
            }

            groups[key].push_back(s);
        }

        vector<vector<string>> result;
        for (auto& [key, group] : groups) {
            result.push_back(group);
        }
        return result;
    }
};
Java 21
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 (char c : s.toCharArray()) {
                count[c - 'a']++;
            }

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append(count[i]);
                sb.append('#');
            }
            String key = sb.toString();

            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

        return new ArrayList<>(groups.values());
    }
}
Python 3.12
from collections import defaultdict


def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)

    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        key = tuple(count)
        groups[key].append(s)

    return list(groups.values())
Go 1.26
import "fmt"

func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)

    for _, s := range strs {
        var count [26]int
        for _, c := range s {
            count[c-'a']++
        }

        key := fmt.Sprint(count)
        groups[key] = append(groups[key], s)
    }

    result := make([][]string, 0, len(groups))
    for _, group := range groups {
        result = append(result, group)
    }
    return result
}

Frequently asked questions

What is the optimal time complexity of Group Anagrams?

The most efficient approach in this guide ("Character Count as Key") runs in O(n * k) where n is the number of strings and k is the maximum string length time and uses O(n * k) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Group Anagrams use?

Group Anagrams is a medium-level Arrays & Hashing problem involving String, Hash Table, Sorting. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Group Anagrams be solved without extra space?

The most space-efficient approach in this guide uses O(n * k) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n * k), while the optimized version uses O(n * k).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Valid Anagram

Original problem: leetcode.com

Loading editor...
Input
strs=
["eat","tea","tan","ate","nat","bat"]
Expected Output
[["bat"],["nat","tan"],["ate","eat","tea"]]