Top Interview 150

The Group Anagrams problem involves grouping words that are anagrams of each other. Let’s solve LeetCode 49: Group Anagrams step by step.

🚀 Problem Description

Given an array of strings strs, group all strings that are anagrams.

An anagram is a word or phrase formed by rearranging the letters of another. Both strings must have the same characters in the same frequencies.

💡 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"]]

🏆 JavaScript Solution

The key idea is to use a hash map to group anagrams. Each anagram has the same sorted character sequence, which we can use as the key.

Implementation

var groupAnagrams = function(strs) {
    const map = new Map();

    for (let str of strs) {
        const sortedStr = str.split("").sort().join("");


        if (!map.has(sortedStr)) {
            map.set(sortedStr, []);
        }
        map.get(sortedStr).push(str);
    }

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

🔍 How It Works

  1. Sort Each String:

    • For each string in strs, sort its characters alphabetically.
    • Use the sorted string as the key in the hash map.

  2. Group Strings by Key:

    • If the sorted string is not already a key in the map, add it with an empty array.
    • Append the original string to the array corresponding to the key.

  3. Return Groups:

    • Extract the grouped arrays from the map and return them.

🔑 Complexity Analysis

  • Time Complexity:

    • Sorting each string: O(m⋅nlogn), where n is the average string length and m is the number of strings.
    • Inserting into the hash map: O(m).
    • Total: O(m⋅nlogn).

  • Space Complexity:

    • The hash map stores O(m) keys and values.

📋 Dry Run

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

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

Follow-Up: Faster Grouping Using Character Count

Instead of sorting strings (which costs O(nlogn)), we can use the character count as the key.

Implementation

var groupAnagrams = function(strs) {
    const map = new Map();

    for (let str of strs) {
        const charCount = Array(26).fill(0);

        for (let char of str) {
            charCount[char.charCodeAt(0) - "a".charCodeAt(0)]++;
        }

        const key = charCount.join("#");

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

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

Complexity (Character Count Approach)

  • Time Complexity: O(m⋅n), where m is the number of strings and n is the average string length.

    • Counting characters is O(n).

  • Space Complexity: O(m) for the hash map.

✨ Pro Tips for Interviews

  1. Highlight Trade-Offs:

    • Sorting strings is simpler to implement but slower than using character counts.

  2. Edge Cases:

    • Empty strings: [""].
    • Single-character strings: ["a", "b", "a"].

📚 Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
👉 Valid Anagram - JavaScript Solution

What’s your preferred method to solve this problem? Let’s discuss! 🚀

Study