Group Anagrams

Group strings that are anagrams of each other 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, typically 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"]]

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 only

Approach 1: Sort Characters as Key

Algorithm

Sort the characters of each string and use the sorted string as a key to group anagrams together.

Steps:

Create a hash map with sorted string as key and list of anagrams as value
For each string, sort its characters and use as key
Add original string to the list for that key
Return all values from the hash map

Implementation

Python:

def group_anagrams(strs):
    """
    Group anagrams using sorted characters as key
    Time: O(n*k*log(k)) where n is number of strings, k is average length
    Space: O(n*k)
    """
    anagram_groups = {}
    
    for s in strs:
        # Sort characters to create key
        sorted_str = ''.join(sorted(s))
        
        # Add to group
        if sorted_str not in anagram_groups:
            anagram_groups[sorted_str] = []
        anagram_groups[sorted_str].append(s)
    
    return list(anagram_groups.values())

Java:

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>> anagramGroups = new HashMap<>();
        
        for (String s : strs) {
            // Sort characters to create key
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String sortedStr = new String(chars);
            
            // Add to group
            anagramGroups.computeIfAbsent(sortedStr, k -> new ArrayList<>()).add(s);
        }
        
        return new ArrayList<>(anagramGroups.values());
    }
}

Go:

// groupAnagrams - Group anagrams using sorted characters as key
// Time: O(n*k*log(k))
// Space: O(n*k)
func groupAnagrams(strs []string) [][]string {
    anagramGroups := make(map[string][]string)
    
    for _, s := range strs {
        // Sort characters to create key
        chars := []rune(s)
        sort.Slice(chars, func(i, j int) bool {
            return chars[i] < chars[j]
        })
        sortedStr := string(chars)
        
        // Add to group
        anagramGroups[sortedStr] = append(anagramGroups[sortedStr], s)
    }
    
    // Convert map values to slice
    result := make([][]string, 0, len(anagramGroups))
    for _, group := range anagramGroups {
        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 anagramGroups = {};
    
    for (const s of strs) {
        // Sort characters to create key
        const sortedStr = s.split('').sort().join('');
        
        // Add to group
        if (!anagramGroups[sortedStr]) {
            anagramGroups[sortedStr] = [];
        }
        anagramGroups[sortedStr].push(s);
    }
    
    return Object.values(anagramGroups);
}

C#:

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 anagramGroups = new Dictionary<string, IList<string>>();
        
        foreach (string s in strs) {
            // Sort characters to create key
            char[] chars = s.ToCharArray();
            Array.Sort(chars);
            string sortedStr = new string(chars);
            
            // Add to group
            if (!anagramGroups.ContainsKey(sortedStr)) {
                anagramGroups[sortedStr] = new List<string>();
            }
            anagramGroups[sortedStr].Add(s);
        }
        
        return anagramGroups.Values.ToList();
    }
}

Complexity Analysis

Time Complexity: O(nklog(k)) where n is number of strings, k is average length
Space Complexity: O(n*k) for storing all strings

Approach 2: Character Count as Key

Algorithm

Use character frequency count as key instead of sorting. This can be more efficient for longer strings.

Steps:

Create a hash map with character count as key
For each string, count character frequencies
Use the count pattern as key to group anagrams
Return all groups

Implementation

Python:

def group_anagrams_count(strs):
    """
    Group anagrams using character count as key
    Time: O(n*k)
    Space: O(n*k)
    """
    anagram_groups = {}
    
    for s in strs:
        # Count character frequencies
        count = [0] * 26
        for char in s:
            count[ord(char) - ord('a')] += 1
        
        # Use count as key
        key = tuple(count)
        if key not in anagram_groups:
            anagram_groups[key] = []
        anagram_groups[key].append(s)
    
    return list(anagram_groups.values())

Java:

class Solution {
    /**
     * Group anagrams using character count as key
     * Time: O(n*k)
     * Space: O(n*k)
     */
    public List<List<String>> groupAnagramsCount(String[] strs) {
        Map<String, List<String>> anagramGroups = new HashMap<>();
        
        for (String s : strs) {
            // Count character frequencies
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            
            // Create key from count
            StringBuilder keyBuilder = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                keyBuilder.append('#').append(count[i]);
            }
            String key = keyBuilder.toString();
            
            // Add to group
            anagramGroups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        
        return new ArrayList<>(anagramGroups.values());
    }
}

Go:

// groupAnagramsCount - Group anagrams using character count as key
// Time: O(n*k)
// Space: O(n*k)
func groupAnagramsCount(strs []string) [][]string {
    anagramGroups := make(map[string][]string)
    
    for _, s := range strs {
        // Count character frequencies
        count := make([]int, 26)
        for _, char := range s {
            count[char-'a']++
        }
        
        // Create key from count
        var keyBuilder strings.Builder
        for i := 0; i < 26; i++ {
            keyBuilder.WriteString(fmt.Sprintf("#%d", count[i]))
        }
        key := keyBuilder.String()
        
        // Add to group
        anagramGroups[key] = append(anagramGroups[key], s)
    }
    
    // Convert map values to slice
    result := make([][]string, 0, len(anagramGroups))
    for _, group := range anagramGroups {
        result = append(result, group)
    }
    
    return result
}

JavaScript:

/**
 * Group anagrams using character count as key
 * Time: O(n*k)
 * Space: O(n*k)
 */
function groupAnagramsCount(strs) {
    const anagramGroups = {};
    
    for (const s of strs) {
        // Count character frequencies
        const count = new Array(26).fill(0);
        for (const char of s) {
            count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        
        // Create key from count
        const key = count.join('#');
        
        // Add to group
        if (!anagramGroups[key]) {
            anagramGroups[key] = [];
        }
        anagramGroups[key].push(s);
    }
    
    return Object.values(anagramGroups);
}

C#:

public class Solution {
    /// <summary>
    /// Group anagrams using character count as key
    /// Time: O(n*k)
    /// Space: O(n*k)
    /// </summary>
    public IList<IList<string>> GroupAnagramsCount(string[] strs) {
        var anagramGroups = 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']++;
            }
            
            // Create key from count
            var keyBuilder = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                keyBuilder.Append('#').Append(count[i]);
            }
            string key = keyBuilder.ToString();
            
            // Add to group
            if (!anagramGroups.ContainsKey(key)) {
                anagramGroups[key] = new List<string>();
            }
            anagramGroups[key].Add(s);
        }
        
        return anagramGroups.Values.ToList();
    }
}

Complexity Analysis

Time Complexity: O(n*k) where n is number of strings, k is average length
Space Complexity: O(n*k) for storing all strings

Key Insights

Anagram Property: Two strings are anagrams if they have the same character frequency
Key Generation: Can use sorted characters or character count as key
Trade-offs: Sorting is simpler but count is more efficient for longer strings
Hash Map: Use hash map to group strings by their key
Edge Cases: Handle empty strings and single character strings

Edge Cases

Empty strings: Array containing empty strings
Single character: Strings with one character
All identical: All strings are the same
No anagrams: Each string is unique
Single string: Array with one string

Test Cases

# Test cases
assert group_anagrams(["eat","tea","tan","ate","nat","bat"]) == [["bat"],["nat","tan"],["ate","eat","tea"]]
assert group_anagrams([""]) == [[""]]
assert group_anagrams(["a"]) == [["a"]]
assert group_anagrams(["abc", "bca", "cab"]) == [["abc", "bca", "cab"]]
assert group_anagrams(["a", "b", "c"]) == [["a"], ["b"], ["c"]]

Follow-up Questions

Anagram Substring Search: Find all anagrams of a pattern in a text
Valid Anagram: Check if two strings are anagrams
Anagram Groups Count: Count number of anagram groups
Longest Anagram Group: Find the largest group of anagrams
Anagram Pairs: Find all pairs of anagrams

Common Mistakes

Key generation: Incorrect sorting or counting logic
Hash map usage: Not properly handling key creation
Edge cases: Not handling empty strings or single characters
Return format: Incorrect return type or structure
Character counting: Off-by-one errors in frequency counting

Interview Tips

Start with examples: Walk through the grouping process
Discuss approaches: Compare sorting vs counting approaches
Handle edge cases: Always consider empty strings and single characters
Optimize when needed: Mention count approach for longer strings
Explain complexity: Discuss time and space complexity trade-offs

Variations

Case-insensitive: Ignore case differences
Extended ASCII: Handle extended character set
Unicode: Support Unicode characters
Custom alphabet: Handle custom character sets
Anagram distance: Find minimum operations to make strings anagrams