Jumble Puzzle Bins

Mediumhash mapAlso known as Group Anagrams

You set the weekly word jumble for a local paper. The best puzzles are sets of words built from exactly the same letters, like least, slate and stale: readers get the scrambled letters and must find every word.

Readers mail in word suggestions, and you have a long list of them. You want to sort them into bins, one bin per set of letters, so you can see at a glance which bins are big enough for a puzzle.

Your task

Write groupJumbles(words). Put two words in the same bin exactly when one is a rearrangement of the other: the same letters, each used the same number of times. Return the list of bins.

Order matters, so the answer is unique. Bins appear in the order their first word appears in words. Inside a bin, words keep their order from words. If a word is suggested twice, both copies go in its bin. An empty list gives [].

groupJumbles(words: string[]) → string[][]

Examples

Example 1

Input

words = ["least", "tea", "slate", "eat", "bus", "stale", "ate"]

Output

[["least", "slate", "stale"], ["tea", "eat", "ate"], ["bus"]]

Whyleast, slate and stale share the letters a, e, l, s, t. tea, eat and ate share a, e, t. bus matches nothing and gets a bin of its own. The bins come in the order of their first words: least, then tea, then bus.

Example 2

Input

words = ["ton", "not", "onto"]

Output

[["ton", "not"], ["onto"]]

Whyonto uses the same three kinds of letter as ton, but it has two o's and four letters, so it is not a rearrangement. It goes in its own bin.

Constraints

0 ≤ words.length ≤ 10,000
0 ≤ words[i].length ≤ 20
Words contain only lowercase letters a to z.

Start with brute force

For each word, compare it with the first word of every bin so far, using a letter-count check like the one in Same Letter Tiles. Put it in the first bin that matches, or start a new bin.

If most words are different, each word is compared with almost every bin, so this costs about n² comparisons. With 10,000 words that is around 50 million word comparisons, each reading up to 20 letters.

Hints

0 of 4 shown

Hint 1
Take slate and least. If you sort the letters of each word alphabetically, what do you get?
Hint 2
Every rearrangement of the same letters sorts to the same string, and words with different letters never do. So the sorted letters work as a label for the bin.
Hint 3
Now you need to go from a label to its bin in one step, while keeping bins in the order they were first created. Which structure maps a key to a list?
Hint 4
Walk the words once. For each word, build its label (sorted letters, or 26 letter counts joined into a string). Look the label up in a map of label → bin. If it is missing, create an empty bin, add it to the map and to your result list. Then append the word to its bin.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

The brute force compares words with each other. Instead, give every word a label that is the same for all its rearrangements and different for everything else. Then grouping is just "put each word in the bin with its label", one map lookup per word.

Sorting the letters makes a good label. Trace [least, tea, slate, eat, bus, stale, ate]:

least → label aelst. New: create bin 1.
tea → aet. New: create bin 2.
slate → aelst. Bin 1 is now [least, slate].
eat → aet. Bin 2 is now [tea, eat].
bus → bsu. New: create bin 3.
stale → bin 1, ate → bin 2. Result: [[least, slate, stale], [tea, eat, ate], [bus]].

The label must capture how many of each letter, not just which letters. A set of letters puts aab with abb, and a sum of letter codes puts ad with bc. Sorted letters, or a string of 26 counts, get both right.

Reference solution

function groupJumbles(words) {
  const binOf = new Map(); // sorted letters -> that bin
  const bins = [];
  for (const w of words) {
    const label = [...w].sort().join("");
    if (!binOf.has(label)) {
      binOf.set(label, []);
      bins.push(binOf.get(label)); // same list object, so order is kept
    }
    binOf.get(label).push(w);
  }
  return bins;
}

def group_jumbles(words):
    bin_of = {}  # sorted letters -> that bin
    bins = []
    for w in words:
        label = "".join(sorted(w))
        if label not in bin_of:
            bin_of[label] = []
            bins.append(bin_of[label])  # same list object, so order is kept
        bin_of[label].append(w)
    return bins

TimeO(n · L log L)Each of the n words is sorted once, where L is the longest word (at most 20). A 26-count label makes it O(n · L).

SpaceO(n · L)The map and the bins together hold every word and one label per bin.

Learn the idea: Hash Tables Strings

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code