LeetCode 49 - Group Anagrams

This is a Medium string and hash map problem: group the input strings by anagram class. This solution uses each string’s sorted form as the dictionary key and appends the original string to that key’s group.

---

Problem link and explanation

• Problem link: 49. Group Anagrams
• Summary: Given an array of strings, return the strings grouped by anagram membership.

An anagram uses the same characters with the same counts, only in a different order. For example, eat, tea, and ate all use one e, one a, and one t, so they belong in the same group.

For this input:

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

One valid result is:

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

The order of the groups does not matter, and the order inside each group does not matter either. The important part is choosing a stable representation for strings that contain the same characters.

---

Approach

The original order of characters gets in the way when comparing anagrams. eat and tea look different, but after sorting, both become aet. That sorted string can represent the whole anagram group.

sorted_str = "".join(sorted(str))

Python’s sorted function sorts the string character by character and returns a list. Joining that list gives a string that can be used as a dictionary key. Every string in the same anagram group produces the same key.

Then defaultdict keeps the grouping code small. Accessing a missing key creates an empty list automatically, so the original string can be appended without a separate existence check.

groups = defaultdict(list)

for str in strs:
    sorted_str = "".join(sorted(str))
    groups[sorted_str].append(str)

eat maps to aet, and tea and ate map to the same key. tan and nat map to ant. bat maps to abt and stays in its own group.

At the end, the grouped values are converted back into a two-dimensional list.

return list(groups.values())

The useful part of this approach is that it avoids comparing every pair of strings. Each word is transformed once, then placed directly into the group for its sorted key.

---

Complexity analysis

Let N be the number of strings and L be the maximum length of a string.

• Time complexity: O(N × L log L)

  • The algorithm visits each string once, and each string is sorted. More precisely, the sorting cost is Σ Li log Li across all strings. Using the maximum word length L, this is bounded by O(N × L log L).

• Space complexity: O(N × L)

  • The hash map stores sorted string keys and grouped string lists. The returned result contains all original strings, and the generated keys can also grow with the total input size.

Sorting each word also creates temporary storage for that word’s characters and sorted key. That temporary space is proportional to the current word length, while the stored groups and keys scale with the total input size.

---

Implementation code

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)

        for str in strs:
            sorted_str = "".join(sorted(str))
            groups[sorted_str].append(str)

        return list(groups.values())

---

Summary and reflection

This problem becomes simpler once an anagram group is represented by a shared key instead of repeated pairwise comparisons. Sorting removes the original character order and leaves a stable representation of the character composition.

The sorted-key approach costs O(N × L log L) time, so it can be more expensive than a fixed-size character-count key when the character set is constrained. The trade-off is clarity: the implementation is short, and the grouping rule is easy to read. In this solution, defaultdict handles group creation, and the sorted string acts as the representative value for each anagram class.