Find Dictionary Words Represented by Repeated Letters
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Find all dictionary words that could produce a supplied string by repeating characters in place. For example, `help` can produce `heellp` by repeating e and l.
Implement `matching_repeated_words(text: string, dictionary: string[]) -> string[]`.
### Constraints & Assumptions
The report describes ignoring repeated letters without a precise stretching rule. This practice contract permits each original character occurrence to repeat one or more times, with no minimum stretch length. It never deletes, reorders, or changes a character.
- Text and words contain lowercase ASCII letters. Empty strings are allowed.
- Dictionary entries are unique and total dictionary length is at most 1000000; text length is at most 100000. Return matching words in dictionary input order.
- Consecutive equal characters form a run. A word matches exactly when it has the same run characters in the same order as text and each word-run length is at most the corresponding text-run length.
- Repeated letters already present in a dictionary word remain meaningful: `hellp` can match `heellp`, but `heeellp` cannot, because its e-run is longer than the supplied string's.
- The empty word matches only empty text.
### Example
```text
text = "heellp"
dictionary = ["help","hellp","heelp","heeellp","heap"]
result = ["help","hellp","heelp"]
```
Explain why simply comparing sets of letters loses order and why collapsing runs without checking their lengths accepts words that could not expand to the input. Give time and memory complexity for comparing many dictionary entries.
```hint Compare runs rather than individual duplicated positions
A run has both a character and a count. The character sequence must agree, and expansion only increases the count.
```
Overview: Match dictionary words to a repeated-letter string using ordered run characters and count inequalities, with explicit stretch, duplicate, and empty-string semantics.
Read the full Waymo Software Engineer interview experience this question came from
Find all dictionary words that could produce a supplied string by repeating characters in place. For example, `help` can produce `heellp` by repeating e and l.
Implement `matching_repeated_words(text: string, dictionary: string[]) -> string[]`.
### Constraints & Assumptions
The report describes ignoring repeated letters without a precise stretching rule. This practice contract permits each original character occurrence to repeat one or more times, with no minimum stretch length. It never deletes, reorders, or changes a character.
- Text and words contain lowercase ASCII letters. Empty strings are allowed.
- Dictionary entries are unique and total dictionary length is at most 1000000; text length is at most 100000. Return matching words in dictionary input order.
- Consecutive equal characters form a run. A word matches exactly when it has the same run characters in the same order as text and each word-run length is at most the corresponding text-run length.
- Repeated letters already present in a dictionary word remain meaningful: `hellp` can match `heellp`, but `heeellp` cannot, because its e-run is longer than the supplied string's.
- The empty word matches only empty text.
### Example
```text
text = "heellp"
dictionary = ["help","hellp","heelp","heeellp","heap"]
result = ["help","hellp","heelp"]
```
Explain why simply comparing sets of letters loses order and why collapsing runs without checking their lengths accepts words that could not expand to the input. Give time and memory complexity for comparing many dictionary entries.
```hint Compare runs rather than individual duplicated positions
A run has both a character and a count. The character sequence must agree, and expansion only increases the count.
```
Constraints
- Text and unique dictionary words use lowercase ASCII letters; empty strings are allowed.
- Text length is at most 100000 and total dictionary length at most 1000000; there is no separate entry-count limit.
- Each original character occurrence may repeat one or more times; no deletion, reordering or substitution is allowed.
- Run characters must match in order and each word-run length must not exceed the corresponding text run.
- The empty word matches only empty text. Return matches unchanged in dictionary order.
Examples
Input: ('heellp', ['help', 'hellp', 'heelp', 'heeellp', 'heap'])
Expected Output: ['help', 'hellp', 'heelp']
Explanation: Word runs may expand but cannot shrink or change characters.
Input: ('aa', ['a', 'aa', 'aaa', ''])
Expected Output: ['a', 'aa']
Explanation: Two-character runs permit stretching with no minimum of three.