Shortest Completing Word
Find the shortest word covering a licence plate's letters, using character counts rather than sets
Problem Statement
Given a string licensePlate and an array of words, find the shortest completing word.
A word is completing if it contains all the letters of the licence plate, respecting multiplicity. Digits and spaces in the plate are ignored, and comparison is case-insensitive. If several words tie on length, return the one that appears first in the array.
Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
Output: "steps"
Why: the plate needs s, p, s, t — that is TWO s's
"step" has only one s → not completing
"steps" has two s's ✓ and is the shortest such word
Input: licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
Output: "pest"Intuition
Multiplicity is the whole difficulty
The plate "1s3 PSt" contains s, P, S, t — after lowercasing, that is two s characters. A completing word needs at least two s characters too.
Using a set of required letters would accept "step", which has only one s. Sets discard multiplicity. This problem needs counts.
The key insight
Reduce the plate to a count map of its letters, ignoring digits and spaces. Then a word completes the plate when, for every required letter, the word's count is at least the plate's count.
That is a multiset containment test, and it is the whole problem.
Note the asymmetry: the word may contain extra letters and extra copies. Only the required letters impose a floor.
Watch it run
Approach
Count the plate's letters
Lowercase, skip anything that is not a letter.
Test containment
Every required letter must appear at least as many times in the word.
Keep the shortest passing word
Use a strict < comparison so the first of several equal-length matches wins.
Solution
from collections import Counter
def shortest_completing_word(license_plate: str, words: list[str]) -> str:
"""Shortest word containing all the plate's letters, with multiplicity."""
required = Counter(char.lower() for char in license_plate if char.isalpha())
best: str | None = None
for word in words:
counts = Counter(word.lower())
# Every required letter must appear at least `need` times.
if all(counts[letter] >= need for letter, need in required.items()):
# Strict < keeps the FIRST word among equal-length matches.
if best is None or len(word) < len(best):
best = word
return best or ""Python's Counter supports the containment test directly:
def shortest_completing_word_subtract(
license_plate: str, words: list[str]
) -> str:
required = Counter(c.lower() for c in license_plate if c.isalpha())
completing = [w for w in words if not required - Counter(w.lower())]
return min(completing, key=len) if completing else ""required - Counter(word) keeps only the shortfalls; an empty result means the word covers everything.
Use `<`, never `<=`, when tracking the shortest
<= would replace an earlier match with a later one of the same length, breaking the "first in the array wins" tie-break rule. This is a one-character bug that only shows up on tied inputs.
Why `counts[letter]` is safe in Python
Indexing a missing key on a Counter returns 0 rather than raising — which is exactly the behaviour needed for "the word has none of this letter". A plain dict would raise KeyError, so use .get(letter, 0) there. TypeScript's Map needs the explicit ?? 0.
Complexity Analysis
Time Complexity
O(n × L)
Space Complexity
O(1)
Where n is the number of words and L is the average word length.
- Time — counting the plate is
O(|plate|), and each word is counted and checked inO(L). - Space — every count map is bounded by the 26 letters, so it does not grow with input size.
Edge Cases
Related Problems
- Valid Anagram — exact multiset equality rather than containment
- Keyboard Row — filtering words by a character condition
- Longest Palindrome — another problem driven purely by character counts