LeetCode Problem #49

solution.md

Group Anagrams - LeetCode Problem #49

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

Problem Understanding

An anagram is a word formed by rearranging the letters of another word (e.g., "eat", "tea", "ate" are all anagrams).

Example:

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

---

Approach 1: Categorize by Sorted String (Most Common)

The key insight: anagrams have the same characters when sorted.

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  
  for (const str of strs) {
    // Sort characters to create a canonical key
    const key = str.split('').sort().join('');
    
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key)!.push(str);
  }
  
  return Array.from(map.values());
}

Time Complexity: O(n × k log k) where n = strings, k = avg length
Space Complexity: O(n × k)

---

Approach 2: Character Count Signature (Optimal)

Instead of sorting, count character frequencies — this is O(n × k) without the sort overhead.

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  
  for (const str of strs) {
    // Create 26-character count array
    const count = new Array(26).fill(0);
    
    for (const char of str) {
      count[char.charCodeAt(0) - 97]++;
    }
    
    // Convert to string key like "a1b2c1..."
    const key = count.join('#');
    
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key)!.push(str);
  }
  
  return Array.from(map.values());
}

Time Complexity: O(n × k)
Space Complexity: O(n × k)

---

Visual Comparison

flowchart LR
    A["Input: eat, tea, tan, nat, bat"] --> B[Character Counting]
    
    B --> C["eat → a1e1t1"]
    B --> D["tea → a1e1t1"]
    B --> E["tan → a1n1t1"]
    B --> F["bat → a1b1t1"]
    
    C & D --> G["Group 1: eat, tea"]
    E --> H["Group 2: tan, nat"]
    F --> I["Group 3: bat"]

Loading

---

When to Use Which Approach?

Approach	Best For
Sorted String	Simpler code, smaller strings
Character Count	Larger strings, performance-critical

Both are interview-favorite solutions. The character count approach is slightly more impressive as it shows awareness of algorithmic optimization!