Find Dictionary Words Represented by Repeated Letters

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 = "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.

Find Dictionary Words Expandable to a Repeated-Character Text

Approach

Encode the text once as consecutive runs of (character,count). Scan each dictionary word by its own runs without constructing a second encoding. Its next run must have the same character as the corresponding text run and no larger count; after the word ends it must have consumed all text runs. Necessity follows because repeating existing occurrences preserves run order and only increases run lengths. Sufficiency follows because any positive word-run length can be expanded to any larger target-run length by distributing additional copies among its occurrences. Empty encodings therefore match exactly each other. Comparing only letter sets loses order, while comparing only collapsed runs ignores the prohibition on shrinking a word run. Emit passing words during dictionary scanning to preserve order. For text length T, total dictionary characters D and N entries, work is O(T+D+N), with early failures potentially reducing it. Python/JavaScript/C++ store O(number of text runs) entries; the Java arrays reserve O(T) capacity. Output storage and C++ copied strings are additional.

• Time complexity: O(text length + total dictionary length + entry count)
• Space complexity: O(text length) upper bound for text runs, plus output