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.

Example:
Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]
Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

Approach: Hash Map with Character Frequencies

While sorting each string to use as a hash map key works (taking $O(m \cdot n \log n)$ time), a more optimal approach is to count the character frequencies for each string. Since the problem limits inputs to lowercase English letters, we can use an array of size 26 to tally the letters, serialize that array into a string, and use it as a unique key in our hash map.

1. Initialize a Hash Map map where keys will be the serialized frequency arrays, and values will be arrays of grouped strings.
2. Iterate through each string str in the input array strs.
3. For each string, initialize an array of size 26 (filled with 0) to represent the frequency of characters from ‘a’ to ‘z’.
4. Iterate through the characters of the current string. Increment the corresponding index in the frequency array (char.charCodeAt(0) - 97).
5. Convert the frequency array into a string (e.g., using .join(',')). This serialized string becomes the unique signature (key) for all anagrams of that word.
6. Push the original string str into the array corresponding to that key in the Hash Map.
7. Finally, extract and return all the grouped arrays using Object.values(map).

Solution

function groupAnagrams(strs) {
    const map = {};
    
    for (let str of strs) {
        const count = new Array(26).fill(0);
        
        for (let char of str) {
            count[char.charCodeAt(0) - 97]++;
        }
        
        const key = count.join(',');
        
        if (!map[key]) {
            map[key] = [];
        }
        
        map[key].push(str);
    }
    
    return Object.values(map);
}

Complexity Analysis

• Time Complexity: $O(m \cdot n)$ where $m$ is the number of strings and $n$ is the maximum length of a string. We iterate through every string and every character exactly once.
• Space Complexity: $O(m \cdot n)$. In the worst case, every string is unique and we store all $m$ strings (each of length $n$) in the hash map.