MediumHash TableStringSorting

Group Anagrams

2 approaches, code in all languages

You are given a list of lowercase words. Two words belong together when one can be produced by shuffling the letters of the other, using every letter exactly as many times. Your job is to partition the list into buckets so that each bucket holds precisely the words that are rearrangements of one another.

Return the collection of buckets. The buckets may appear in any order, and the words inside a single bucket may also be listed in any order.

Example 1

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

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

"eat", "tea", and "ate" share the same letters, so they land in one bucket. "tan" and "nat" form another, and "bat" stands alone.

Example 2

Input: strs = ["abc","bca","xyz"]

Output: [["abc","bca"],["xyz"]]

"abc" and "bca" are rearrangements of each other; "xyz" matches nothing else.

Constraints

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] contains only lowercase English letters

Sorted String As Key

Sort the characters of each word to build a canonical key, then group words that share the same key in a hash map.

Loading animation…

Intuition

Any two anagrams contain the identical multiset of letters, so if you sort each word alphabetically you get the same sorted string for every member of a group. That sorted string is a perfect fingerprint: use it as a hash-map key and every word that reduces to it drops into the same list. Collecting the map's values at the end gives you the buckets.

Algorithm walkthrough

1Create an empty hash map that maps a canonical key to a list of original words.
2For each word, sort its characters to produce the key string.
3Append the original word to the list stored under that key, creating the list if the key is new.
4After every word is placed, take all the lists held in the map.
5Return those lists as the grouped result.

Implementation

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        for s in strs:
            key = ''.join(sorted(s))
            groups.setdefault(key, []).append(s)
        return list(groups.values())

Time

O(n * k log k)

Space

O(n * k)

n is the number of words and k is the maximum word length; the log k factor comes from sorting each word.

Character Count Signature

Build a key from the per-letter frequency of each word instead of sorting, giving linear-time key construction.

Loading animation…

Intuition

Anagrams share not only the same letters but the same count of every letter. Instead of paying to sort, count occurrences of each of the 26 letters and serialize that count vector into a string. Two words produce the same signature exactly when they are anagrams, so the same signature groups them together in the map.

Algorithm walkthrough

1Prepare a hash map keyed by a frequency signature string.
2For each word, tally how many times each of the 26 letters appears.
3Turn that tally into a delimited string so different counts never collide.
4Append the word to the list under its signature.
5Return all the lists collected in the map.

Implementation

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        for s in strs:
            count = [0] * 26
            for ch in s:
                count[ord(ch) - ord('a')] += 1
            key = tuple(count)
            groups.setdefault(key, []).append(s)
        return list(groups.values())

Time

O(n * k)

Space

O(n * k)

Counting letters is linear per word, so building keys avoids the sort's log factor.

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI