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

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! 🚀