Partition Words Into Groups With Identical Letter Counts

Given a list of lowercase words, partition them into groups so that two words are in the same group exactly when one can be turned into the other by reordering its letters, that is, when both contain every letter the same number of times. In the interview this was discussed verbally, with the time and space complexity of the approach; here it is a function to implement. ### Function Signature ```python def group_by_letters(words: list[str]) -> list[list[str]]: ``` ### Rules - Two words belong to the same group if and only if, for every letter from `a` to `z`, they contain that letter the same number of times. Empty strings form one group together. - Every element of `words` appears in exactly one group, once per occurrence: duplicate words stay as separate entries of the same group. - Within a group, words appear in the order in which they appear in `words`. - Groups are ordered by the position in `words` of their first word. ### Constraints - `1 <= len(words) <= 10^4` - `0 <= len(words[i]) <= 100` - Every word consists only of lowercase English letters `a` to `z`. ### Examples **Example 1** ```text Input: words = ["listen", "google", "silent", "enlist", "gogole", "cat"] Output: [["listen", "silent", "enlist"], ["google", "gogole"], ["cat"]] ``` `listen`, `silent` and `enlist` use the same six letters once each. `google` and `gogole` each contain two `g`, two `o`, one `l` and one `e`. The groups are ordered by their first words, at positions 0, 1 and 5. **Example 2** ```text Input: words = ["", "b", "", "ab", "ba", "b"] Output: [["", ""], ["b", "b"], ["ab", "ba"]] ``` Duplicates stay in their group once per occurrence, and the two empty strings form a group. The first words of the groups are at positions 0, 1 and 3. **Example 3** ```text Input: words = ["aab", "aba", "abb", "baa"] Output: [["aab", "aba", "baa"], ["abb"]] ``` `abb` uses the same two letters as `aab` but in different counts, so it forms its own group.