Partition Words Into Groups With Identical Letter Counts
Company: Workday
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Overview: Partition a list of lowercase words into groups whose members contain exactly the same letters the same number of times, keeping words and groups in input order. Tests hashing-based grouping, handling of duplicates and empty strings, and analysis of time and space complexity for many short strings.
Read the full Workday Software Engineer interview experience this question came from
Given a list of lowercase words `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.
Implement `group_by_letters(words)`, which returns the groups as a list of lists of words.
**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.
These rules fix a single correct output for every input.
**Constraints**
- `1 <= len(words) <= 10^4`
- `0 <= len(words[i]) <= 100`
- Every word consists only of lowercase English letters `a` to `z` (the empty string is allowed).
**Example 1**
```
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**
```
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.
Constraints
- 1 <= len(words) <= 10^4
- 0 <= len(words[i]) <= 100
- Every word consists only of lowercase English letters a to z; the empty string is allowed.
Examples
Input: (['listen', 'google', 'silent', 'enlist', 'gogole', 'cat'],)
Expected Output: [['listen', 'silent', 'enlist'], ['google', 'gogole'], ['cat']]
Explanation: Source Example 1: groups start at positions 0, 1 and 5; google and gogole both have two g, two o, one l and one e.
Input: (['', 'b', '', 'ab', 'ba', 'b'],)
Expected Output: [['', ''], ['b', 'b'], ['ab', 'ba']]
Explanation: Source Example 2: the duplicate b is kept twice and the two empty strings form the first group; groups start at positions 0, 1 and 3.
Hints
- Whether two words belong together depends only on how many times each letter a to z occurs in them, not on where those letters sit.
- Both the order of the groups and the order inside each group follow the input order, so nothing in the output needs to be sorted.
- Empty strings and repeated words are valid input: every occurrence must appear exactly once in the output.