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 ```python 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`.