Bucket Words That Are Letter Rearrangements of One Another

You are given a list of lowercase words. Partition them into groups so that two words are in the same group exactly when one can be formed by rearranging the letters of the other, meaning both contain the same letters with the same counts. Return the groups in a fixed canonical order.

The interview used a variation of this classic task whose twist was not reported; this version is the standard task with a fully specified output order.

Function Signature

def group_letter_rearrangements(words: list[str]) -> list[list[str]]:

Rules

• Every input word appears in exactly one group. Duplicate words are kept: if a word occurs twice in the input, it occurs twice in its group.
• The empty string is a valid word; all empty strings form one group together.
• Within each group, sort the words in ascending lexicographic order (ordinary string comparison).
• Order the groups by their first word, ascending. Different groups always have different first words, so this order is unique.

Constraints

• 1 <= len(words) <= 10^4
• 0 <= len(words[i]) <= 100
• Each word contains only the lowercase letters a to z.

Examples

Example 1

words = ["stop", "pots", "tops", "opt", "top", "pot"]
output = [["opt", "pot", "top"], ["pots", "stop", "tops"]]

stop, pots and tops share the letters o, p, s, t; opt, top and pot share o, p, t. The group starting with opt comes first because opt sorts before pots.

Example 2

words = ["", "b", ""]
output = [["", ""], ["b"]]

Both empty strings form one group, which sorts before the group starting with b.

Example 3

words = ["listen", "silent", "enlist", "google", "gogole", "cat"]
output = [["cat"], ["enlist", "listen", "silent"], ["gogole", "google"]]

gogole sorts before google because their third letters are g and o.