Group Anagrams

Given an array of strings, group the anagrams together.

Language Selection

Choose your preferred programming language

Showing: Python

Group Anagrams

Problem Statement

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, 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: "eat", "tea", and "ate" are anagrams. "tan" and "nat" are anagrams. "bat" has no anagram partner.

Example 2:

Input: strs = [""]
Output: [[""]]
Explanation: A single empty string forms its own group.

Example 3:

Input: strs = ["a"]
Output: [["a"]]
Explanation: A single character string forms its own group.

Constraints

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters only

Approach 1: Sorted String as Key

Algorithm

Sort the characters of each string and use the sorted result as a hash map key. All anagrams produce the same sorted string, so they naturally group together.

Steps:

Create a hash map where the key is a sorted string and the value is a list of original strings
For each string, sort its characters to form the key
Append the original string to the corresponding list in the map
Return all the values from the hash map

Implementation

Python:

from collections import defaultdict

def groupAnagrams(strs):
    """
    Group anagrams using sorted characters as key
    Time: O(n * k log k) where n = number of strings, k = max string length
    Space: O(n * k) to store all strings in the map
    """
    groups = defaultdict(list)

    for s in strs:
        # Sort characters to create canonical key
        key = ''.join(sorted(s))
        groups[key].append(s)

    return list(groups.values())

Java:

import java.util.*;

class Solution {
    /**
     * Group anagrams using sorted characters as key
     * Time: O(n * k log k)
     * Space: O(n * k)
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String s : strs) {
            // Sort characters to create canonical key
            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());
    }
}

Go:

import "sort"

// groupAnagrams - Group anagrams using sorted characters as key
// Time: O(n * k log k)
// Space: O(n * k)
func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)

    for _, s := range strs {
        // Sort characters to create canonical key
        chars := []rune(s)
        sort.Slice(chars, func(i, j int) bool {
            return chars[i] < chars[j]
        })
        key := string(chars)

        groups[key] = append(groups[key], s)
    }

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

    return result
}

JavaScript:

/**
 * Group anagrams using sorted characters as key
 * Time: O(n * k log k)
 * Space: O(n * k)
 */
function groupAnagrams(strs) {
    const groups = new Map();

    for (const s of strs) {
        // Sort characters to create canonical key
        const key = s.split('').sort().join('');

        if (!groups.has(key)) {
            groups.set(key, []);
        }
        groups.get(key).push(s);
    }

    return Array.from(groups.values());
}

C#:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    /// <summary>
    /// Group anagrams using sorted characters as key
    /// Time: O(n * k log k)
    /// Space: O(n * k)
    /// </summary>
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var groups = new Dictionary<string, IList<string>>();

        foreach (string s in strs) {
            // Sort characters to create canonical key
            char[] chars = s.ToCharArray();
            Array.Sort(chars);
            string key = new string(chars);

            if (!groups.ContainsKey(key)) {
                groups[key] = new List<string>();
            }
            groups[key].Add(s);
        }

        return groups.Values.ToList<IList<string>>();
    }
}

Complexity Analysis

Time Complexity: O(n * k log k) where n is the number of strings and k is the maximum string length. Sorting each string costs O(k log k).
Space Complexity: O(n * k) to store all strings in the hash map

Approach 2: Character Count as Key (Optimal)

Algorithm

Instead of sorting, build a character frequency count for each string and use it as the hash map key. This avoids the O(k log k) sorting cost per string.

Steps:

For each string, count the frequency of each of the 26 lowercase letters
Convert the frequency array to a hashable key (tuple, delimited string, etc.)
Group strings by their frequency key
Return all groups

Implementation

Python:

from collections import defaultdict

def groupAnagrams(strs):
    """
    Group anagrams using character count as key
    Time: O(n * k) where n = number of strings, k = max string length
    Space: O(n * k)
    """
    groups = defaultdict(list)

    for s in strs:
        # Count character frequencies
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1

        # Use tuple of counts as key (tuples are hashable)
        key = tuple(count)
        groups[key].append(s)

    return list(groups.values())

Java:

import java.util.*;

class Solution {
    /**
     * Group anagrams using character count as key
     * Time: O(n * k)
     * Space: O(n * k)
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String s : strs) {
            // Count character frequencies
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }

            // Build delimited string key from counts
            StringBuilder keyBuilder = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                keyBuilder.append('#').append(count[i]);
            }
            String key = keyBuilder.toString();

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

        return new ArrayList<>(groups.values());
    }
}

Go:

import (
    "fmt"
    "strings"
)

// groupAnagrams - Group anagrams using character count as key
// Time: O(n * k)
// Space: O(n * k)
func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)

    for _, s := range strs {
        // Count character frequencies
        var count [26]int
        for _, ch := range s {
            count[ch-'a']++
        }

        // Build delimited string key from counts
        var keyBuilder strings.Builder
        for i := 0; i < 26; i++ {
            keyBuilder.WriteString(fmt.Sprintf("#%d", count[i]))
        }
        key := keyBuilder.String()

        groups[key] = append(groups[key], s)
    }

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

    return result
}

JavaScript:

/**
 * Group anagrams using character count as key
 * Time: O(n * k)
 * Space: O(n * k)
 */
function groupAnagrams(strs) {
    const groups = new Map();

    for (const s of strs) {
        // Count character frequencies
        const count = new Array(26).fill(0);
        for (const ch of s) {
            count[ch.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }

        // Use delimited string as key
        const key = count.join('#');

        if (!groups.has(key)) {
            groups.set(key, []);
        }
        groups.get(key).push(s);
    }

    return Array.from(groups.values());
}

C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Solution {
    /// <summary>
    /// Group anagrams using character count as key
    /// Time: O(n * k)
    /// Space: O(n * k)
    /// </summary>
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var groups = new Dictionary<string, IList<string>>();

        foreach (string s in strs) {
            // Count character frequencies
            int[] count = new int[26];
            foreach (char c in s) {
                count[c - 'a']++;
            }

            // Build delimited string key from counts
            var keyBuilder = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                keyBuilder.Append('#').Append(count[i]);
            }
            string key = keyBuilder.ToString();

            if (!groups.ContainsKey(key)) {
                groups[key] = new List<string>();
            }
            groups[key].Add(s);
        }

        return groups.Values.ToList<IList<string>>();
    }
}

Complexity Analysis

Time Complexity: O(n * k) where n is the number of strings and k is the maximum string length. Counting characters is O(k) per string.
Space Complexity: O(n * k) to store all strings in the hash map

Key Insights

Canonical Form: Anagrams share a canonical form – either a sorted string or a character frequency signature. This is the key to grouping them.
Sorted Key vs Count Key: Sorting costs O(k log k) per string; counting costs O(k). For long strings, the counting approach is faster.
Hash Map Grouping: The hash map naturally collects all strings that share the same canonical key into the same bucket.
Key Encoding: In languages without hashable arrays (Java, Go, JS), encode the count array as a delimited string to use as a map key.
Order Does Not Matter: The output groups can appear in any order, and elements within each group can appear in any order.

Edge Cases

Empty Strings: [""] – a single group containing one empty string
All Identical: [“aaa”, “aaa”, “aaa”] – all in one group
No Anagrams: [“abc”, “def”, “ghi”] – each string in its own group
Single String: [“word”] – one group with one element
Mixed Lengths: [“ab”, “abc”, “ba”] – “ab” and “ba” group together; “abc” is separate
Single Characters: [“a”, “b”, “a”] – “a” and “a” group together; “b” is separate

Test Cases

def test_groupAnagrams():
    # Standard case
    result = groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
    result_sets = [set(group) for group in result]
    assert set(frozenset(g) for g in result_sets) == {
        frozenset({"eat", "tea", "ate"}),
        frozenset({"tan", "nat"}),
        frozenset({"bat"})
    }

    # Single empty string
    assert groupAnagrams([""]) == [[""]]

    # Single character
    assert groupAnagrams(["a"]) == [["a"]]

    # No anagrams
    result2 = groupAnagrams(["abc", "def", "ghi"])
    assert len(result2) == 3

    # All identical strings
    result3 = groupAnagrams(["aaa", "aaa", "aaa"])
    assert len(result3) == 1
    assert len(result3[0]) == 3

    # Mixed lengths
    result4 = groupAnagrams(["ab", "abc", "ba", "bca"])
    result4_sets = [set(group) for group in result4]
    assert set(frozenset(g) for g in result4_sets) == {
        frozenset({"ab", "ba"}),
        frozenset({"abc", "bca"})
    }

    print("All tests passed!")

test_groupAnagrams()

Follow-up Questions

Valid Anagram: How would you check if just two strings are anagrams? (LeetCode #242)
Find All Anagram Substrings: Given a string and a pattern, find all starting indices where an anagram of the pattern begins (LeetCode #438)
Largest Anagram Group: Return only the largest group of anagrams
Streaming Input: How would you handle strings arriving one at a time?
Case Insensitive: How would you modify the solution if uppercase and lowercase letters are treated as the same?

Common Mistakes

Non-Hashable Keys: Using a list or array directly as a dictionary key in Python (lists are not hashable; use tuples instead)
Delimiter Collisions: When encoding count arrays as strings, failing to use a delimiter, e.g., counts [1, 2, 3] and [12, 3] could both produce “123” without a separator
Forgetting Empty Strings: Not handling the case where strs[i] is an empty string, which should still form a valid group
Modifying Input: Sorting the original string in place instead of creating a copy
Wrong Complexity Analysis: Claiming O(n) time while ignoring the O(k log k) or O(k) cost per string

Interview Tips

Start with Sorted Key: The sorted-key approach is intuitive and easy to explain
Optimize to Count Key: After presenting the sorted approach, mention the count-key optimization for bonus points
Walk Through an Example: Trace “eat”, “tea”, “ate” to show that sorting each produces “aet”
Discuss Key Encoding: Explain why delimiters are needed when converting count arrays to strings
Mention Time Complexity: Be precise – O(n * k log k) for sorting vs O(n * k) for counting

Concept Explanations

Canonical Form: Two objects are equivalent if and only if they map to the same canonical form. For anagrams, the canonical form is either the sorted character sequence or the character frequency distribution.

Hash Map Grouping Pattern: This is a common pattern: compute a key for each item, and use a hash map to collect items with the same key. It appears in many grouping and partitioning problems.

Key Encoding Trade-offs: In Python, tuples are hashable and can serve directly as dictionary keys. In Java, Go, and JavaScript, you must serialize the frequency array into a string. Using a delimiter like ‘#’ prevents ambiguity.

Sorting vs Counting: Sorting is simpler to implement but costs O(k log k) per string. Counting costs O(k) per string but requires more careful key encoding. For short strings (k <= 100), the difference is small; for longer strings, counting wins.

Language Selection

Group Anagrams

Problem Statement

Examples

Constraints

Approach 1: Sorted String as Key

Algorithm

Implementation

Complexity Analysis

Approach 2: Character Count as Key (Optimal)

Algorithm

Implementation

Complexity Analysis

Key Insights

Edge Cases

Test Cases

Follow-up Questions

Common Mistakes

Interview Tips

Concept Explanations

Share this