Group Anagrams

Problem Description

Given an array of strings strs, group the anagrams together. Return the answer in any order.

Examples

Constraints

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

Anagrams Have Identical Canonical Forms

The problem reduces to finding a canonical representation that all anagrams of a word share. Any two strings that are anagrams of each other should map to the same key. The two candidates are: sort the string (O(k log k) per word), or build a frequency count tuple (O(k) per word). Either one works as a hash map key.

Solution 1: Sort Each String as the Key

Sort every string and use the sorted version as the key. “eat”, “tea”, and “ate” all sort to “aet”, so they land in the same bucket.

import java.util.*;

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);
            // sorted string is the canonical key for this anagram group
            String key = new String(chars);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        groups = defaultdict(list)
        for s in strs:
            # sorted tuple is the canonical key for this anagram group
            key = tuple(sorted(s))
            groups[key].append(s)
        return list(groups.values())

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
        std::unordered_map<std::string, std::vector<std::string>> groups;
        for (const std::string& s : strs) {
            std::string key = s;
            // sorted string is the canonical key for this anagram group
            std::sort(key.begin(), key.end());
            groups[key].push_back(s);
        }
        std::vector<std::vector<std::string>> result;
        for (auto& [key, group] : groups) {
            result.push_back(std::move(group));
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n * k log k). For each of the n strings we sort in O(k log k) where k is the max string length.
• Space Complexity: O(n * k). Storing all strings in the hash map.

Where it breaks: if k is large (say, 100 characters), sorting adds log k overhead per string. For very long strings, the frequency-count key approach below eliminates the sort cost.

Solution 2: Character Count as Key

Instead of sorting, build a 26-element frequency count and use it as the key. This reduces key generation from O(k log k) to O(k).

import java.util.*;

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']++;
            // serialize the count array into a string key
            StringBuilder key = new StringBuilder();
            for (int freq : count) key.append(freq).append('#');
            groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        groups = defaultdict(list)
        for s in strs:
            # frequency tuple as key avoids the sort entirely
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            groups[tuple(count)].append(s)
        return list(groups.values())

#include <vector>
#include <string>
#include <unordered_map>

class Solution {
public:
    std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
        std::unordered_map<std::string, std::vector<std::string>> groups;
        for (const std::string& s : strs) {
            int count[26] = {};
            for (char c : s) count[c - 'a']++;
            // serialize count array as a delimited string key
            std::string key;
            for (int f : count) key += std::to_string(f) + '#';
            groups[key].push_back(s);
        }
        std::vector<std::vector<std::string>> result;
        for (auto& [key, group] : groups) result.push_back(std::move(group));
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n * k). Building the count array for each string is O(k), and we do it n times.
• Space Complexity: O(n * k). Same map storage as before.

Where it breaks: the key serialization must include delimiters (like #) between counts. Without them, [1, 11] and [11, 1] would serialize to the same string “111”, causing incorrect grouping.

Common Mistakes

• Missing delimiters in the count key. Counts [1, 11] and [11, 1] both stringify to “111” without a separator. Always use a delimiter character between count values.
• Using a list as a dictionary key in Python. Lists aren’t hashable. Convert the count array to a tuple before using it as a key.
• Expecting a specific output order. The problem says “any order,” so don’t add sorting logic to match a specific arrangement.

Frequently Asked Questions

Which solution should I present first in an interview? Start with the sorted string approach since it’s immediately readable. Then offer the count-key approach as a follow-up optimization when the interviewer asks how you’d improve it.

Does the order of groups in the output matter? No. The problem explicitly says the answer can be returned in any order, and the groups themselves can be in any order too.

What if two strings in the same group appear in a different order in the output? Also fine. ”[“eat”,“tea”,“ate”]” and ”[“ate”,“tea”,“eat”]” are both correct answers for that group.

← All Problems