49. Group Anagrams

[!info] Problem Link: LeetCode - Group Anagrams

📝 Problem Description

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

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

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

💡 Approaches & Explanations

Approach 1: Categorize by Sorted String

Two strings are anagrams if and only if their sorted versions are equal. We can use a hash map where the key is the sorted string and the value is a list of anagrams.

Time Complexity: \mathcal{O}(N \cdot K \log K) where N is the number of strings and K is the maximum length of a string.
Space Complexity: \mathcal{O}(N \cdot K)

Approach 2: Categorize by Character Count — Optimal

Instead of sorting, we can represent each string as a frequency array of size 26 (for 'a' to 'z'). Two strings are anagrams if their frequency arrays are identical.

Initialize a hash map res.
For each string in strs:
- Create a count array of size 26, initialized to 0.
- For each character in the string, increment its corresponding index in the count array.
- Convert the count array to a tuple (to make it hashable) and use it as a key in res.
- Append the original string to the list at that key.
Return res.values().

📊 Complexity Analysis

Time Complexity: \mathcal{O}(N \cdot K) where N is the number of strings and K is the maximum length of a string. We iterate through each string and each character once.
Space Complexity: \mathcal{O}(N \cdot K) to store the result in the hash map.

💻 Code Implementations

Python3

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)  # mapping charCount to list of Anagrams

        for s in strs:
            count = [0] * 26  # a ... z
            for c in s:
                count[ord(c) - ord("a")] += 1
            
            # Convert list to tuple so it can be used as a key in dictionary
            res[tuple(count)].append(s)
            
        return list(res.values())

🧠 Key Takeaways & Lessons

Hashing Frequency Arrays: Using a frequency array as a hash map key is a common technique for string problems where order doesn't matter (like anagrams).
Tuple conversion: In Python, lists are mutable and cannot be used as dictionary keys. Converting them to tuples (which are immutable) solves this.
Asymptotic Optimization: While sorting is often "fast enough," the character count approach is asymptotically superior for long strings.

3.3 KiB Raw Permalink Blame History