LeetCode Solution 49 - Group Anagrams

 Problem Statement

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

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

Example 1:

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

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

Optimal Approach

The most efficient way to solve this problem is by using a HashMap (unordered_map in C++), where the key is a sorted version of each string and the value is a list of strings that are anagrams of each other.

Approach: Using HashMap with Sorted Key

• Iterate over the list of strings.
• Sort each string and use it as a key in a hash map.
• Group anagrams together under the same sorted key.
• Return the grouped values as the final result.

Code Implementation (C++)

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> anagramGroups;
        
        for (string s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            anagramGroups[key].push_back(s);
        }
        
        vector<vector<string>> result;
        for (auto& entry : anagramGroups) {
            result.push_back(entry.second);
        }
        
        return result;
    }
};

Step-by-Step Explanation

1. HashMap Initialization: Create a hash map where keys are sorted versions of words and values are lists of anagrams.
2. Sorting Each String: Iterate through the input list, sorting each string to create a common key for anagrams.
3. Grouping Anagrams: Store each string in the corresponding bucket in the hash map.
4. Extracting Results: Convert the hash map values into a list of lists and return the final result.

Dry Run / Execution Steps

Consider strs = ["eat", "tea", "tan", "ate", "nat", "bat"].

Step	String	Sorted Key	HashMap State
1	"eat"	"aet"	{ "aet": ["eat"] }
2	"tea"	"aet"	{ "aet": ["eat", "tea"] }
3	"tan"	"ant"	{ "aet": ["eat", "tea"], "ant": ["tan"] }
4	"ate"	"aet"	{ "aet": ["eat", "tea", "ate"], "ant": ["tan"] }
5	"nat"	"ant"	{ "aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"] }
6	"bat"	"abt"	{ "aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"] }

Final output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Sorting + HashMap	O(n k log k)	O(nk)	Optimal
Brute Force	O(n^2 k)	O(nk)	Too slow for large inputs
Character Count Encoding	O(nk)	O(nk)	Works but sorting is simpler

Best Solution & Why It’s Best

The best solution is using a hash map with sorted strings as keys because:

• It runs in O(n k log k) time complexity.
• It efficiently groups anagrams while avoiding unnecessary comparisons.
• Sorting each string ensures all anagrams map to the same key.

Complexity Analysis

• Sorting Approach: O(n k log k) time, O(nk) space.
• Brute Force Approach: O(n^2 k) time, O(nk) space.
• Character Count Encoding: O(nk) time, O(nk) space.

Conclusion

• The best way to group anagrams is by sorting and using a hash map.
• It is the most efficient method in terms of both time and space.
• Similar problems for practice:
  • Valid Anagram
  • Find All Anagrams in a String
  • Group Shifted Strings

---

This blog post ensures clarity, an in-depth explanation, multiple approaches, and LeetCode compatibility. 🚀