LeetCode 49: Group Anagrams Solution in Python Explained

Problem Statement

LeetCode 49, Group Anagrams, is a medium-level problem where you’re given an array of strings strs. Your task is to group all the anagrams together and return them as a list of lists. Anagrams are strings that contain the same characters with the same frequencies, rearrangeable into each other (e.g., "eat" and "tea"). The result can be in any order.

Constraints

1 <= strs.length <= 10^4: Array length is between 1 and 10,000.
0 <= strs[i].length <= 100: Each string’s length is between 0 and 100.
strs[i] consists of lowercase English letters.

Example

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
Explanation: "eat", "tea", "ate" are anagrams; "tan", "nat" are anagrams; "bat" is alone.

Input: strs = [""]
Output: [[""]]
Explanation: Empty string is its own anagram.

Input: strs = ["a"]
Output: [["a"]]
Explanation: Single character is its own anagram.

Understanding the Problem

How do you solve LeetCode 49: Group Anagrams in Python? For strs = ["eat","tea","tan","ate","nat","bat"], group them into [["eat","tea","ate"],["tan","nat"],["bat"]]. Anagrams share the same character composition, so we need a way to identify and group them efficiently. We’ll explore two approaches: a HashMap with Sorted Strings Solution (optimal and primary) and an Alternative with Character Count (also efficient but different). The sorted strings method uses sorting as a key to group anagrams in O(n * k * log k) time.

Solution 1: HashMap with Sorted Strings Approach (Primary)

Explanation

Use a hash map where the key is the sorted version of each string (since anagrams sort to the same string), and the value is a list of strings that match that key. Iterate through strs, sort each string, and append it to its corresponding group in the map.

Here’s a flow for ["eat","tea","tan","ate","nat","bat"]:

"eat" -> "aet" -> ["eat"]
"tea" -> "aet" -> ["eat","tea"]
"tan" -> "ant" -> ["tan"]
...
Result: [["eat","tea","ate"],["tan","nat"],["bat"]]

Initialize HashMap.

Map sorted string to list of anagrams.

Process Strings.

Sort each string, group in map.

Return Groups.

Extract values from map.

Step-by-Step Example

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

We need [["eat","tea","ate"],["tan","nat"],["bat"]].

Goal: Group anagrams.
Result for Reference: [["eat","tea","ate"],["tan","nat"],["bat"]].
Start: strs = ["eat","tea","tan","ate","nat","bat"], hash_map = {}.
Step 1: "eat".

Sort: "aet", hash_map["aet"] = ["eat"].

Step 2: "tea".

Sort: "aet", hash_map["aet"] = ["eat","tea"].

Step 3: "tan".

Sort: "ant", hash_map["ant"] = ["tan"].

Step 4: "ate".

Sort: "aet", hash_map["aet"] = ["eat","tea","ate"].

Step 5: "nat".

Sort: "ant", hash_map["ant"] = ["tan","nat"].

Step 6: "bat".

Sort: "abt", hash_map["abt"] = ["bat"].

Finish: hash_map = {"aet":["eat","tea","ate"], "ant":["tan","nat"], "abt":["bat"]}, return values.

Example 2: strs = [""]

We need [[""]].

Start: hash_map = {}.
Step 1: "".

Sort: "", hash_map[""] = [""].

Finish: Return [[""]].

How the Code Works (Sorted Strings)

Here’s the Python code with line-by-line explanation:

from collections import defaultdict

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    # Line 1: Initialize hash map with defaultdict
    hash_map = defaultdict(list)

    # Line 2: Process each string
    for s in strs:
        # Line 3: Sort string as key
        key = ''.join(sorted(s))
        # Line 4: Append to corresponding group
        hash_map[key].append(s)

    # Line 5: Return all groups
    return list(hash_map.values())

Alternative: Character Count Approach

Explanation

Use a hash map where the key is a tuple of character counts (e.g., frequency of each letter a-z), and the value is the list of anagrams. This avoids sorting by counting occurrences, which can be faster for small alphabets.

Initialize HashMap.
Count Characters.

Build a count array/tuple for each string.

3. Group Anagrams. 4. Return Groups.

Step-by-Step Example (Alternative)

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

Start: hash_map = {}.
Step 1: "eat".

Count: (1,0,0,0,1,0,...,1,0) (a,e,t), hash_map[(1,0,...,1)] = ["eat"].

Step 2: "tea".

Same count, hash_map[(1,0,...,1)] = ["eat","tea"].

Step 3: "tan".

Count: (1,0,...,1,0,...,1) (a,n,t), hash_map[(1,0,...,1)] = ["tan"].

Step 4: Continue, group all.
Finish: Return [["eat","tea","ate"],["tan","nat"],["bat"]].

How the Code Works (Character Count)

from collections import defaultdict

def groupAnagramsCount(strs: list[str]) -> list[list[str]]:
    # Line 1: Initialize hash map
    hash_map = defaultdict(list)

    # Line 2: Process each string
    for s in strs:
        # Line 3: Create character count array
        count = [0] * 26
        for char in s:
            count[ord(char) - ord('a')] += 1
        # Line 4: Use tuple of counts as key
        key = tuple(count)
        hash_map[key].append(s)

    # Line 5: Return all groups
    return list(hash_map.values())

Complexity

Sorted Strings:

Time: O(n * k * log k) – n strings, k = max string length, sorting each string.
Space: O(n * k) – Store all strings in hash map.

Character Count:

Time: O(n * k) – Linear pass per string, fixed 26 characters.
Space: O(n * k) – Store strings, O(1) per key.

Efficiency Notes

Character Count is O(n * k) time, slightly faster for small alphabets (like lowercase letters), while Sorted Strings is O(n * k * log k) but simpler to code. Both use O(n * k) space, suitable for LeetCode 49.

Key Insights

Tips to master LeetCode 49:

Anagram Key: Sorted string or char count identifies groups.
HashMap Power: Group efficiently with dictionary.
Edge Handling: Empty strings and single chars are anagrams.

Additional Example

For strs = ["cat","tac","act"]:

Goal: [["cat","tac","act"]].
Sorted: All sort to "act", hash_map["act"] = ["cat","tac","act"].
Result: [["cat","tac","act"]].

Edge Cases

Empty Array: [] – Return [[]].
All Empty: ["",""] – Return [["",""]].
No Anagrams: ["a","b"] – Return [["a"],["b"]].

Final Thoughts

The HashMap with Sorted Strings solution is a clean win for LeetCode 49 in Python—intuitive, efficient, and easy to implement. For a related challenge, try LeetCode 48: Rotate Image to switch to matrix manipulation! Ready to group some anagrams? Solve LeetCode 49 on LeetCode now and test it with ["eat","tea","ate"] or ["a","b","c"] to perfect your grouping skills. Dive in and sort it out!