5.group-anagrams.md

Group Anagrams

The Group Anagrams problem is a popular coding interview question that checks your understanding of string manipulation and hashing techniques. The core idea is to identify and group strings that are anagrams of each other.

In this article, we'll go over the problem statement, walk through two approaches with code, and analyze their time and space complexity.

---

🔍 Problem Statement

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

What is an Anagram?

An anagram is a word or phrase formed by rearranging the letters of another word. For example:

• "listen" and "silent"

• "eat", "tea", "ate"

---

🧪 Example

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

---

🧠 Approach 1: Using a Sorted Key

Sort each word's characters alphabetically and use the result as a key in a hash map. All words with the same sorted key are anagrams.

✅ JavaScript Code

/**
 * Groups anagrams by sorting each word.
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = new Map();

    for (let word of strs) {
        const key = word.split('').sort().join('');
        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key).push(word);
    }

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

⏱ Complexity

• Time Complexity: O(n * k log k)

  • n: number of strings

  • k: average length of each string

  • Sorting takes O(k log k) per string

• Space Complexity: O(nk)

  • Storing all strings in a hash map

---

⚡️ Approach 2: Using Character Count as Key

Instead of sorting, count the number of each character in the string and use that as the key.

✅ JavaScript Code

/**
 * Groups anagrams using character frequency count as key.
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = new Map();

    for (let word of strs) {
        const count = new Array(26).fill(0);
        for (let char of word) {
            count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        const key = count.join('#'); // use a delimiter to prevent collisions
        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key).push(word);
    }

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

⏱ Complexity

• Time Complexity: O(n * k)

  • Count array computation is O(k), and you do it for each of n strings

• Space Complexity: O(nk)

  • Count arrays as keys and store all grouped strings

---

🤔 Which Approach is Better?

Approach	Time Complexity	Pros	Cons
Sorted Key	O(n * k log k)	Easy to implement	Slower due to sorting
Character Count	O(n * k)	Faster for large inputs	Slightly more complex

✅ Use character count approach for optimal performance, especially with longer strings.

---

🧷 Notes & Edge Cases

• Strings can be empty: [""] → [[""]]

• Single characters: ["a"] → [["a"]]

• All strings are unique (no anagram pairs): return each in a separate group

---

🔗 Reference

LeetCode: Group Anagrams