FastPrepDictionary Matches from Repeated Letters
Problems/Dictionary Matches from Repeated Letters

Dictionary Matches from Repeated Letters

Waymo logoWaymo● MediumFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The onsite report gives a repeated-letter string such as heellp and dictionary word help, asking for all dictionary words obtainable by ignoring repeats. Run-count comparison formalizes that seed and matches it at about 94%.

The string typed was formed by taking a word and repeating each character one or more consecutive times. For every word in dictionary, determine whether deleting only extra copies inside runs of typed can produce that word.

Return matching dictionary entries in their original order. Duplicates in the dictionary remain duplicated.

Function

expandedWordMatches(typed: String, dictionary: String[]) → String[]

Examples

Example 1

typed = "heellp"dictionary = ["help","heelp","hello"]return = ["help","heelp"]

Each matching run uses no more copies than typed provides.

Example 2

typed = "aaabb"dictionary = ["ab","aab","aaabb","abbc"]return = ["ab","aab","aaabb"]

The a and b run counts may independently shrink but not vanish.

Example 3

typed = "abc"dictionary = ["abc","abbc","ac"]return = ["abc"]

No run has an extra copy to remove.

Constraints

  • 1 <= typed.length <= 10^5.
  • The total dictionary character count is at most 2 * 10^5.
  • All strings contain lowercase English letters.

More Waymo problems

  • Fixed-Order Task Run Time With CooldownPHONE SCREEN · Seen Oct 2026
  • Reorderable Task Scheduler With CooldownPHONE SCREEN · Seen Oct 2026
  • Island Area and Water BoundaryPHONE SCREEN · Seen Sep 2026
All Waymo interview questionsSee Waymo hiring insights
Saved
class Solution {
    public String[] expandedWordMatches(String typed, String[] dictionary) {
        // Write your solution here.
    }
}
Checking account…