Shortest Completing Word

Shortest Completing Word

What is this problem about?

The Shortest Completing Word interview question gives you a license plate string and a list of words. Find the shortest word in the list that contains all the letters in the license plate (ignoring digits, spaces, and case). If multiple words have the same minimum length and contain all required letters, return the first one. This is a letter frequency matching problem.

Why is this asked in interviews?

Google asks this problem because it tests character frequency counting, case-insensitive matching, and clean comparison logic. It validates that candidates can use a Counter (or frequency array) to check if one frequency map is a subset of another, and can handle the "first minimum" requirement correctly. The problem models text completion systems and keyword matching in autocomplete engines.

Algorithmic pattern used

The pattern is frequency map comparison. Extract letters from the license plate (ignoring non-alphabetic characters), convert to lowercase, and build a frequency counter. For each word in the list, build a frequency counter of its letters. Check if the word's counter "covers" the license plate counter: for every letter in the license plate counter, the word must have at least as many occurrences. Track the shortest covering word; return the first one found when there are ties.

Example explanation

licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"].

Letters in plate (lowercase): s, p, s, t → frequency: {s:2, p:1, t:1}.

• "step": {s:1, t:1, e:1, p:1}. s=1 < 2 → ✗.
• "steps": {s:2, t:1, e:1, p:1}. s:2≥2, p:1≥1, t:1≥1 → ✓. Length 5.
• "stripe": s:1 < 2 → ✗.
• "stepple": covers all. Length 7 > 5.

Return: "steps".

Common mistakes candidates make

• Not ignoring digits, spaces, and punctuation in the license plate — only letters count.
• Using case-sensitive comparison — convert both plate and words to lowercase before frequency counting.
• Returning the last matching word instead of the first when lengths tie — iterate in order and keep the first minimum.
• Using Counter(plate) directly without filtering non-letter characters.

Interview preparation tip

For the Shortest Completing Word coding problem, the hash table string interview pattern is the straightforward approach. Python's Counter makes frequency comparison elegant: all(word_counter[c] >= plate_counter[c] for c in plate_counter). Google interviewers use this as a 5-minute warm-up — solve it cleanly, then discuss follow-ups: "What if words can also contain digits?" or "How would you optimize for repeated license plate queries?" Practice Counter-based subset checking — it appears in anagram, scramble, and character containment problems throughout interview preparation.