Shortest Completing Word

EasyArrays & Hashinghashing

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a string licensePlate and an array of lowercase words words. Ignore every digit and space in licensePlate, and treat its letters case-insensitively. A completing word is a word that contains every letter from licensePlate at least as many times as it appears there. For example, if the plate is "aBc 12c", a completing word needs at least one a, one b, and two cs. Return the shortest completing word. If several completing words share the shortest length, return the one that appears first in words. At least one completing word is guaranteed to exist.

Examples

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"
The plate needs s twice, p, and t. "step" has only one s; "steps" is the shortest that works.
Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
Output: "pest"
Only an s is needed; "pest", "stew", and "show" tie at length 4 and "pest" comes first.

Constraints

  • 1 <= licensePlate.length <= 7
  • `licensePlate` contains digits, letters (either case), or spaces
  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 15
  • `words[i]` consists of lowercase English letters

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More hashing problems