Group Anagrams

+10

You get a list of words strs. Two words are anagrams when one is a rearrangement of the other: the same letters, each used the same number of times. Put every word in a group with all of its anagrams, and return one string per group: the group's words in alphabetical order, joined by single spaces. Order the groups alphabetically by their first word.

A word that appears twice is listed twice in its group, and a word with no anagram forms a group of one. Alphabetical means dictionary order: aab comes before ab, and ab before abc.

Function

groupAnagrams(strs: string-array) → string-array

strsstring-array: the words to group, lowercase letters only
Returnsstring-array: one string per group: its words sorted and joined by spaces, groups ordered by their first word

Constraints

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
Every word holds lowercase English letters only.

Examples

Input: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
Output: ["apple", "enlist listen silent", "notes onset stone tones"]
Explanation: enlist, listen and silent each use e, i, l, n, s and t once. notes, onset, stone and tones share e, n, o, s and t, and apple matches nothing. By first word the groups run apple, enlist, notes.

Input: strs = ["race", "arc", "care", "car", "acre"]
Output: ["acre care race", "arc car"]
Explanation: acre, care and race share a, c, e and r. arc and car have no e, so they form their own group. acre comes before arc because c comes before r at the second letter.

Input: strs = ["b", "a", "b"]
Output: ["a", "b b"]
Explanation: The two copies of b are anagrams of each other, and both stay in the group. a has no partner and comes first.

+15 hidden tests on Submit

Follow-up

Suppose the words could hold any Unicode characters instead of 26 lowercase letters. Which of the two keys, sorted letters or letter counts, still works, and what would you change in it?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Comparing every word with every other word works, but it spends a full comparison on each pair. What cracks the problem is a canonical key: a value you compute from one word alone that is the same for all of its anagrams and different for every other word. A word's letters in sorted order are such a key, and a hash map from key to group turns the grouping into a single pass. The required order comes for free if you sort the words before you group them.

Compare each word with every group

Correct, but does not finish on the largest tests

Intuition

Being anagrams is transitive: if stone matches notes and notes matches tones, then stone matches tones. So a new word never needs to meet every member of a group. Comparing it with the group's first word decides whether it belongs there.

To compare two words, count letters. They are anagrams when they have the same length and every letter appears as often in one as in the other. Add 1 for each letter of the first word and subtract 1 for each letter of the second, and check that all 26 counters end at 0.

Sort the input first, and the order takes care of itself. Words arrive alphabetically, each one joins the end of its group, so every group stays sorted. A group is created when its alphabetically first word arrives, so the groups are already ordered by first word.

The cost is the scan. When no two words are anagrams, each word is compared with every group before it: 4000 words make about 4000 × 3999 / 2 ≈ 8 × 10^6 comparisons, each touching up to 8 letters and 26 counters. That is too slow for Python, Lua and R on the largest tests, and the work grows with the square of the list, so it would sink any language at 10^5 words.

Algorithm

Sort the words alphabetically.
Keep a list of groups, each a list of words.
For each word, look for a group whose first word has the same letter counts, and append the word to it.
If no group matches, start a new group holding only this word.
Join each group's words with single spaces and return the groups in the order you created them.

def is_anagram(a, b):
    # Same length, and every letter appears as often in a as in b.
    if len(a) != len(b):
        return False
    counts = [0] * 26
    for c in a:
        counts[ord(c) - 97] += 1
    for c in b:
        counts[ord(c) - 97] -= 1
    return all(x == 0 for x in counts)


def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = []
    for word in sorted(strs):
        for group in groups:
            if is_anagram(group[0], word):
                group.append(word)
                break
        else:
            groups.append([word])
    return [" ".join(group) for group in groups]

Group by sorted letters in a hash map

Intuition

Instead of asking which group a word matches, compute the group's name from the word itself. Sort a word's letters and all of its anagrams give the same text: listen, silent and enlist all become eilnst, while stone becomes enost. Two words share a sorted form exactly when they hold the same letters the same number of times, which is the definition of an anagram. So the sorted form is a canonical key for the group.

A hash map from key to list of words then groups everything in one pass. Each word costs one sort of at most 8 letters and one map lookup, and it is never compared with another group.

For the order, sort the input before grouping, as in the first approach. Words arrive alphabetically, so each list fills up in order, and a key enters the map when its group's first word arrives. Maps that keep insertion order (a Python dict, a JavaScript Map, a Java LinkedHashMap, a Dart map, Ruby hashes and PHP arrays) hand the groups back in that order. Where the map has no order, store each group's index in the map and the groups themselves in a list.

Sorting the input takes about n log n comparisons of up to k letters, roughly 5 × 10^4 word comparisons for 4000 words instead of 8 × 10^6. Building the keys adds O(n · k log k), which is small next to it because k ≤ 8.

Algorithm

Sort the words alphabetically.
For each word, build its key by sorting its letters.
Look the key up in a hash map. If it is new, start an empty group for it, keeping the groups in the order you create them.
Append the word to its key's group.
Return each group's words joined by single spaces, groups in creation order.

def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = {}  # key (the letters in sorted order) -> the group's words
    for word in sorted(strs):
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    # A dict keeps insertion order, so the groups come out by first word.
    return [" ".join(words) for words in groups.values()]

Pitfalls and edge cases

The grouping is the part people practise. Most wrong answers on this version come from the order of the output and from keys that are not unique.

Ordering the groups by their key instead of their first word. A key is the smallest rearrangement of its words, not one of them: for ["cab", "bad"] the keys are abc and abd, which would put cab first, but by first word bad comes first.
Collecting words in a set. ["b", "a", "b"] must give b b; a set keeps one copy.
A key built from the distinct letters only. ab and aabb use the same two letters, but aabb has two of each, so they are not anagrams.
A key that adds up letter codes. ad and bc have the same sum, so a sum merges words that share no letter.
Sorting each group but not the input, then forgetting to sort the groups. Insertion order is then the order of the input, not of the first words.
Joining by hand and leaving a space at the start or end of a group's string.

Frequently asked questions4

What is the time complexity of Group Anagrams?

With a hash map keyed by sorted letters, building the keys takes O(n · k log k) for n words of up to k letters, and the map work is O(n · k). This version also sorts the words to order the output, which adds O(n · k · log n). Space is O(n · k) for the keys and the groups.

Is a letter count key faster than sorting each word?

A count key, the 26 letter counts written out as text such as 1#0#2#…, takes O(k) time instead of O(k log k), so it wins on long words. With words of at most 8 letters the sort is as fast, and the alphabetical sort of the output costs more than either key. Both keys are correct, because two words have the same counts exactly when they have the same sorted letters.

Why not use the sum of the letter codes as the key?

Different letters can add up to the same total: a + d equals b + c, so ad and bc would land in one group. A key must be equal for anagrams and different for everything else, and the sorted letters or the full count of every letter guarantee that. Multiplying one prime per letter is also exact, but with 101 for z, a word of ten z's already overflows a 64-bit integer.

Why sort the input before grouping?

The answer asks for sorted groups ordered by their first word. Sorting all the words once gives both: each group receives its words alphabetically, and a group is created when its first word arrives. Sorting every group afterwards and then the groups by their first word gives the same result with more code.

Python

def groupAnagrams(strs):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]

Expected

["apple", "enlist listen silent", "notes onset stone tones"]