Group Anagrams

Q: What is the time complexity of Group Anagrams?

Building the sorted-letter keys takes O(n · k log k) for n words of up to k letters, and the map work is O(n · k) . Sorting the words to order the output adds O(n · k · log n) , which dominates. Space is O(n · k) for the keys and the groups.

Q: Is a letter count key faster than sorting each word?

A count key, the 26 letter counts written as text such as 1#0#2#… , takes O(k) instead of O(k log k) , so it wins on long words. At 8 letters or fewer the sort is as fast. Both keys are exact: two words have the same counts exactly when they have the same sorted letters.

MediumHashing Sorting

+10

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

A repeated word 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 use e, i, l, n, s and t once each. notes, onset, stone and tones share e, n, o, s and t. apple matches nothing and, by first word, leads.

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.

Follow-up

If the words could hold any Unicode characters, which key, 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

Compute a key from each 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 collects the groups in one pass. Sort the words first and the required order comes for free.

Compare each word with every group

Correct, but does not finish on the largest tests

Intuition

Keep a list of groups and compare each word with the first word of every group. Being anagrams is transitive, so one comparison per group decides membership. Two words are anagrams when they have the same length and the same count of each of the 26 letters. Sort the input first: each group then fills in alphabetical order, and the groups are created in order of their first word.

When no two words are anagrams, each word meets every group before it: 4000 words make about 8 × 10^6 comparisons, each touching up to 8 letters and 26 counters.

Algorithm

Sort the words alphabetically.
For each word, find a group whose first word has the same letter counts and append the word. If none matches, start a new group.
Return each group's words joined by single spaces, in creation order.

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

Compute the group's name from the word itself. Sort a word's letters and every anagram gives 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. A hash map from key to word list then groups everything in one pass, and no word is compared with another group.

The order comes from sorting the input first, as before: each list fills alphabetically, and a key enters the map when its group's first word arrives. A map that keeps insertion order returns the groups in that order; otherwise keep the groups in a list and map each key to its index.

Sorting the input costs about 5 × 10^4 word comparisons for 4000 words, instead of 8 × 10^6.

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

Ordering the groups by key instead of by first word. For ["cab", "bad"] the keys abc and abd put cab first, but bad should lead.
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 are not anagrams.
Sorting each group but not the input, and not sorting the groups. Insertion order then follows the input, not the first words.

Frequently asked questions3

What is the time complexity of Group Anagrams?

Building the sorted-letter keys takes O(n · k log k) for n words of up to k letters, and the map work is O(n · k). Sorting the words to order the output adds O(n · k · log n), which dominates. 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 as text such as 1#0#2#…, takes O(k) instead of O(k log k), so it wins on long words. At 8 letters or fewer the sort is as fast. Both keys are exact: 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 share a group. A product of one prime per letter is exact, but with 101 for z, a word of ten z's overflows a 64-bit integer.

def groupAnagrams(strs):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

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