MediumHash TableStringSorting

Group Anagrams

2 approaches, code in every language

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 see the solution

You get 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

After the pattern

Now solve one you haven't seen.

Bin Label Families is our own problem on the technique behind Group Anagrams: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free

Group Anagrams

Problem description

Example 1

Example 2

Constraints

Create a free account to see the solution

Now solve one you haven't seen.