deepSWE.io

Group Anagrams

HashingString

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.

Example

Input Array:

"eat"

"tea"

"tan"

"ate"

"nat"

"bat"

↓

Grouped Anagrams:

Key: "aet"

"eat"

"tea"

"ate"

Key: "ant"

"tan"

"nat"

Key: "abt"

"bat"

Group 1: "aet"

Group 2: "ant"

Group 3: "abt"

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

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

Explanation:

"eat", "tea", "ate" are anagrams (same letters: a, e, t)
"tan", "nat" are anagrams (same letters: a, n, t)
"bat" has unique letters and forms its own group

Key Insights

• Anagrams have the same characters with the same frequency
• Sorting characters creates a unique key for each anagram group
• Hash map can efficiently group strings by their sorted key
• Time complexity: O(n * m log m) where n is number of strings, m is average length
• Alternative: Use character frequency count as key

Constraints

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

Algorithm Explanation

This solution uses a hash map to group anagrams efficiently. The key insight is that anagrams have the same characters with the same frequencies, so we can create a unique key for each anagram group.

Key Steps

Create Key: Sort characters of each string to create a unique key.
Group by Key: Use hash map to group strings with the same key.
Collect Groups: Extract all groups from the hash map.
Return Result: Return the grouped anagrams as a list of lists.

Algorithm Analysis

Time Complexity: O(n × m log m) where n is the number of strings and m is the average length
Space Complexity: O(n × m) for storing the hash map and result
Sorting: Each string needs to be sorted to create the key
Alternative: Use character frequency counting for O(n × m) time

Group Anagrams Visualization

Step-by-step grouping of anagram strings

Input Array:

"eat"

"tea"

"tan"

"ate"

"nat"

"bat"

Hash Map (Key → Anagrams)

Hash map is empty

Start: Initialize hash map

Starting to group anagrams using hash map

Step 1 of 20

Currently Processing

Processed

Pending

Code Example

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    """
    Group anagrams using hash map with sorted string as key.
    Time complexity: O(n * m log m) where n is number of strings, m is average length
    Space complexity: O(n * m) for storing the hash map and result
    """
    if not strs:
        return []
    
    # Hash map to store anagram groups
    # Key: sorted string, Value: list of anagrams
    anagram_map = {}
    
    for string in strs:
        # Sort the characters to create a unique key for anagrams
        # All anagrams will have the same sorted key
        sorted_key = ''.join(sorted(string))
        
        # Add the string to the appropriate anagram group
        if sorted_key not in anagram_map:
            anagram_map[sorted_key] = []
        anagram_map[sorted_key].append(string)
    
    # Return all anagram groups as a list of lists
    return list(anagram_map.values())

def groupAnagramsAlternative(strs: List[str]) -> List[List[str]]:
    """
    Alternative solution using character frequency counting.
    Time complexity: O(n * m) where n is number of strings, m is average length
    Space complexity: O(n * m) for storing the hash map and result
    """
    if not strs:
        return []
    
    anagram_map = {}
    
    for string in strs:
        # Count frequency of each character
        char_count = [0] * 26
        for char in string:
            char_count[ord(char) - ord('a')] += 1
        
        # Use tuple of counts as key (lists are not hashable)
        key = tuple(char_count)
        
        if key not in anagram_map:
            anagram_map[key] = []
        anagram_map[key].append(string)
    
    return list(anagram_map.values())