Difficulty: Easy | Acceptance: 63.10% | Paid: No Topics: Array, Hash Table, String
Given a string licensePlate and an array of strings words, find the shortest completing word in words.
A license plate consists of upper case letters, lower case letters, and digits.
A completing word is a word that contains all the letters in the license plate (case insensitive). The letter frequency in the completing word must be greater than or equal to the frequency of the corresponding letter in the license plate. If there are multiple shortest completing words, return the first one.
- Examples
- Constraints
- Frequency Count with Arrays
- Frequency Count with HashMap
- Sorting + Frequency Count
Examples
Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"
Explanation: The license plate has letters 's', 'p', 's', 't'.
The word "steps" contains all these letters and is the shortest among the words that do.
Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
Output: "pest"
Explanation: The license plate has only 's'. The shortest word containing 's' is "pest".
Constraints
1 <= licensePlate.length <= 7
licensePlate contains digits, letters (uppercase or lowercase), and space ' '.
1 <= words.length <= 1000
1 <= words[i].length <= 15
words[i] consists of lowercase English letters.
Frequency Count with Arrays
Intuition Count the frequency of each letter in the license plate using a fixed-size array of 26 elements, then check each word to see if it has at least those frequencies.
Steps
- Create a frequency array of size 26 for the license plate letters
- Iterate through each word and create its frequency array
- Compare the word’s frequency with the license plate’s frequency
- Track the shortest word that satisfies the condition
from typing import List
class Solution:
def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
lp_count = [0] * 26
for c in licensePlate:
if c.isalpha():
lp_count[ord(c.lower()) - ord('a')] += 1
shortest = None
for word in words:
word_count = [0] * 26
for c in word:
word_count[ord(c.lower()) - ord('a')] += 1
completes = True
for i in range(26):
if word_count[i] < lp_count[i]:
completes = False
break
if completes and (shortest is None or len(word) < len(shortest)):
shortest = word
return shortest
Complexity
- Time: O(n × m) where n is the number of words and m is the average word length
- Space: O(1) for the fixed-size frequency arrays
- Notes: Most efficient approach with constant space overhead
Frequency Count with HashMap
Intuition Use a hash map (or Counter in Python) to count letter frequencies, which provides cleaner code at the cost of slightly higher constant factors.
Steps
- Extract only letters from the license plate and count their frequencies
- For each word, count its letter frequencies
- Check if the word has sufficient count for each required letter
- Return the shortest completing word
from typing import List
from collections import Counter
class Solution:
def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
lp_letters = [c.lower() for c in licensePlate if c.isalpha()]
lp_count = Counter(lp_letters)
shortest = None
for word in words:
word_count = Counter(word.lower())
completes = True
for char, count in lp_count.items():
if word_count[char] < count:
completes = False
break
if completes and (shortest is None or len(word) < len(shortest)):
shortest = word
return shortest
Complexity
- Time: O(n × m) where n is the number of words and m is the average word length
- Space: O(k) where k is the number of unique letters in the license plate (at most 26)
- Notes: More readable code with slightly higher constant factors
Sorting + Frequency Count
Intuition Sort words by length first, then find the first completing word. This can be more efficient if we expect to find a match early in the sorted list.
Steps
- Count letter frequencies in the license plate
- Sort words by length (and original index for tie-breaking)
- Iterate through sorted words and return the first completing word
from typing import List
class Solution:
def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
lp_count = [0] * 26
for c in licensePlate:
if c.isalpha():
lp_count[ord(c.lower()) - ord('a')] += 1
sorted_words = sorted(enumerate(words), key=lambda x: (len(x[1]), x[0]))
for idx, word in sorted_words:
word_count = [0] * 26
for c in word:
word_count[ord(c.lower()) - ord('a')] += 1
completes = True
for i in range(26):
if word_count[i] < lp_count[i]:
completes = False
break
if completes:
return word
return ""
Complexity
- Time: O(n log n + n × m) for sorting and checking
- Space: O(n) for storing indices
- Notes: Useful when we want to find the answer quickly after sorting, but adds O(n log n) overhead