Skip to main content

Leetcode 49: Group Anagrams

 

1. Problem Statement (Simple Explanation):


You’re given an array of strings strs.

You must group together all anagrams, where:

  • Two strings are anagrams if one can be rearranged to form the other.

  • You can return groups in any order.

  • The order of strings inside each group doesn’t matter.


2. Examples:


Example 1:


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

Groups:

  • "bat" → ["bat"] (no anagram partners)

  • "nat", "tan" → ["nat","tan"]

  • "eat", "tea", "ate" → ["eat","tea","ate"]

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


Example 2:


Input: strs = [""]`

Output: [[""]]


Example 3:


Input: strs = ["a"]

Output: [["a"]]


3. Approach – Hash Map with Canonical Key:


To group anagrams, we need a way to map all words that are anagrams of each other to the same key.

Two common strategies:

  1. Sort-based key (simple, typical)

  2. Character count-based key (more efficient for long strings)

Given constraints (length up to 100), both are fine. I’ll focus on the sorted-string key; you can mention the count-key as a follow-up optimization.


3.1. Sorted String as Key:


For each string:

  1. Convert it to a char array.

  2. Sort the characters.

  3. Convert back to string → this is the key.

Example:

  • "eat" → "aet"

  • "tea" → "aet"

  • "ate" → "aet"

All three map to the key "aet", so they go into the same group.

We can maintain a map:

  • Map<String, List<String>> groups

  • Key: sorted version of string.

  • Value: list of anagrams.

At the end, return groups.values().


Pseudo-code:



Complexity:


Let:

  • n = number of strings

  • k  = max length of a string

For each string:

  • Sorting cost: O(k*logk)

Total:

  • Time: O(n.klogk)

  • Space: O(n.k) for storing strings & map keys.

This is fine for n <= 104, k <= 100.


3.2. Alternative – Frequency-Count Key (Optimization Idea):


Instead of sorting, we can count frequency of each of 26 letters:

  • E.g., for "eat" and "tea":

    • counts: [1,0,0,0,1,...] (1 a, 1 e, 1 t, others 0)

We can encode this count array as a string key:

key = "1#0#0#0#1#...#"

This makes key generation O(k) instead of O(k log k). For small k, both are fine; this variant is a good optimization to mention.


4. Java code:



5.C code:


(For C on LeetCode, Java/C++/Python/JS are usually preferred for hash map heavy tasks.)



6.C++ code (sorted-key):



7. Python code:



8. JavaScript code:



9. Alternative Implementation – Count-key (Python example):


Comments

Post a Comment