We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Completing Word

Number: 749

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given a licensePlate string and a list of words, find the shortest word from the list that contains every letter (case insensitive and ignoring numbers/spaces) present in the licensePlate. Each letter in the licensePlate must appear in the chosen word at least as many times as it appears in the licensePlate. If there are multiple words of the same shortest length, return the one that appears first in the list.

Key Insights

  • Normalize the licensePlate by converting it to lowercase and filtering out non-letter characters.
  • Create a frequency count (hash table) for the letters in the licensePlate.
  • For each word in the list, count its letters and verify if it meets or exceeds the required frequencies.
  • Maintain tracking of the current shortest word which satisfies the requirement.
  • The licensePlate’s frequency count is fixed (only 26 letters), so we can compare each word’s count efficiently.

Space and Time Complexity

Time Complexity: O(N * L) where N is the number of words and L is the average length of a word, since we iterate through each word and count its letters. Space Complexity: O(1) extra space due to the fixed size (26 letters) of the letter frequency arrays or hash tables used.

Solution

The approach works as follows:

  1. Normalize the licensePlate by converting it to lowercase and filtering out non-letter characters.
  2. Create a frequency dictionary for the filtered licensePlate letters.
  3. For each word in the words list, build a frequency dictionary.
  4. Check whether the word's dictionary has at least the same count for each letter required by the licensePlate's dictionary.
  5. Update the result if the word is shorter than the current best or if it is the first encountered shortest completing word.
  6. Return the result.

This solution leverages hash tables (or fixed size frequency arrays) to efficiently count letter occurrences and uses a direct comparison between the licensePlate frequency count and each word's count.

Code Solutions

# Python solution with detailed comments

def shortestCompletingWord(licensePlate, words):
    # Normalize the licensePlate: filter only alphabet characters and convert to lower-case
    plate_letters = [char.lower() for char in licensePlate if char.isalpha()]
    
    # Build frequency dictionary for the license plate letters
    license_freq = {}
    for char in plate_letters:
        license_freq[char] = license_freq.get(char, 0) + 1
    
    # Function to check if word frequency covers license frequency
    def is_completing(word):
        word_freq = {}
        for c in word:
            word_freq[c] = word_freq.get(c, 0) + 1
        for letter, required_count in license_freq.items():
            if word_freq.get(letter, 0) < required_count:
                return False
        return True
    
    # Initialize result variable with None or a high length word
    shortest_word = None
    
    # Iterate over words in the given list
    for word in words:
        if is_completing(word):
            # Select the word if no word has been chosen yet or it is shorter than the current shortest word
            if shortest_word is None or len(word) < len(shortest_word):
                shortest_word = word
    
    return shortest_word

# Example usage:
print(shortestCompletingWord("1s3 PSt", ["step", "steps", "stripe", "stepple"]))  # Expected output: "steps"
← Back to All Questions