Group Anagrams

MediumAmazonGoogleFacebookMicrosoftApple

Problem

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

Intuition — the key insight

Two strings are anagrams if and only if their sorted versions are identical. Use the sorted string as a HashMap key — all anagrams map to the same key and get grouped together automatically.

Approach

Sorted string as key

For each string, sort its characters to get a canonical key. All anagrams produce the same sorted key. Store groups in a HashMap from key → list of strings.

Complexity

Time

O(n × k log k)

Space

O(n × k)

n strings each of max length k. Sorting each string is O(k log k). HashMap stores all strings.

Solution code

Python

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # or ''.join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

Edge cases to remember

⚠Empty string is its own group with key ''

⚠Single character strings

⚠All strings are anagrams of each other

Hints

What pattern do you think this problem uses?