Taro Logo

Shortest Completing Word

Easy
Asked by:
Profile picture
15 views
Topics:
ArraysStringsTwo Pointers

Given a string licensePlate and an array of strings words, find the shortest completing word in words.

A completing word is a word that contains all the letters in licensePlate. Ignore numbers and spaces in licensePlate, and treat letters as case insensitive. If a letter appears more than once in licensePlate, then it must appear in the word the same number of times or more.

For example, if licensePlate = "aBc 12c", then it contains letters 'a', 'b' (ignoring case), and 'c' twice. Possible completing words are "abccdef", "caaacab", and "cbca".

Return the shortest completing word in words. It is guaranteed an answer exists. If there are multiple shortest completing words, return the first one that occurs in words.

Example 1:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"
Explanation: licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'.
"step" contains 't' and 'p', but only contains 1 's'.
"steps" contains 't', 'p', and both 's' characters.
"stripe" is missing an 's'.
"stepple" is missing an 's'.
Since "steps" is the only word containing all the letters, that is the answer.

Example 2:

Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
Output: "pest"
Explanation: licensePlate only contains the letter 's'. All the words contain 's', but among these "pest", "stew", and "show" are shortest. The answer is "pest" because it is the word that appears earliest of the 3.

Constraints:

  • 1 <= licensePlate.length <= 7
  • licensePlate contains digits, letters (uppercase or lowercase), or space ' '.
  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 15
  • words[i] consists of lower case English letters.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Is the licensePlate case-insensitive, and should I treat upper and lower case letters the same when checking for completeness?
  2. Can the licensePlate or the words array be empty or null? What should I return in those cases?
  3. If there are multiple shortest completing words, can I return any one of them, or is there a specific preference (e.g., the word that appears first in the 'words' array)?
  4. Does completeness require the exact number of occurrences of each character in the licensePlate, or just at least that many?
  5. Are there any special characters or numbers in the licensePlate or the words array, and if so, should I consider those when determining completeness?

Brute Force Solution

Approach

The brute force approach to finding the shortest completing word involves checking every single word against a given license plate. We'll see if each word contains all the letters in the license plate, ignoring case and non-letters. The shortest word that contains all the letters wins.

Here's how the algorithm would work step-by-step:

  1. First, clean up the license plate by removing anything that isn't a letter and making all the letters lowercase.
  2. Next, take the first word from the list of words.
  3. See if the first word contains all the letters from the cleaned-up license plate, ignoring the order of the letters. Essentially, we are checking to see if the word contains all of the letters with at least the same frequency.
  4. If the word doesn't contain all the necessary letters, move to the next word in the list and repeat the previous step.
  5. If the word *does* contain all the necessary letters, remember this word as the current shortest completing word.
  6. Now, continue checking the remaining words in the list.
  7. For each remaining word that contains all the necessary letters, compare its length to the length of the current shortest completing word.
  8. If the new word is shorter, replace the current shortest completing word with this new, shorter word.
  9. After checking all the words, the word you've remembered as the shortest completing word is the answer.

Code Implementation

def shortest_completing_word(license_plate, words):
    normalized_license_plate = ''.join(char.lower() for char in license_plate if char.isalpha())

    shortest_word = None

    for word in words:
        # Check if current word contains all letters
        word_contains_all_letters = True
        for char in set(normalized_license_plate):
            if word.lower().count(char) < normalized_license_plate.lower().count(char):
                word_contains_all_letters = False
                break

        # Update shortest word if applicable
        if word_contains_all_letters:
            if shortest_word is None or len(word) < len(shortest_word):
                # Update shortest_word
                shortest_word = word

    return shortest_word

Big(O) Analysis

Time Complexity
O(L + W * (K + M))Let L be the length of the license plate, W be the number of words, K be the average length of the words, and M be the number of unique characters in the license plate. Cleaning the license plate takes O(L) time. Then, for each of the W words, we check if it contains all characters from the license plate, which takes O(K + M) time, where K is the average length of the words and M is the number of unique characters in the cleaned license plate. Therefore, the overall time complexity is O(L + W * (K + M)).
Space Complexity
O(1)The algorithm uses a cleaned-up version of the license plate, which in the worst case, could have the same number of characters as the original license plate but is bounded by the length of the license plate string. It also stores the current shortest completing word. However, the space used for these is independent of the number of words in the input list. While the length of license plate and shortest word can vary, they don't scale with the size of the word list; therefore, the auxiliary space remains constant. This constant space usage results in a space complexity of O(1).

Optimal Solution

Approach

The task is to find the shortest word from a list that contains all the letters of a given license plate. We achieve this by efficiently checking if a word fulfills the license plate's letter requirements and then selecting the shortest valid word.

Here's how the algorithm would work step-by-step:

  1. First, count how many times each letter appears in the license plate, ignoring numbers, spaces, and capitalization.
  2. Then, for each word in the list of words, check if it contains all the letters from the license plate with at least the required frequency.
  3. To check a word, count the frequency of letters it contains and compare with the license plate letter counts.
  4. If a word contains all the necessary letters, compare its length with the current shortest completing word.
  5. If it's shorter, update the current shortest completing word.
  6. After checking all the words, the last shortest completing word is the answer.

Code Implementation

def shortestCompletingWord(license_plate, words):
    license_plate_letter_counts = {}
    for char in license_plate:
        if char.isalpha():
            lower_char = char.lower()
            license_plate_letter_counts[lower_char] = license_plate_letter_counts.get(lower_char, 0) + 1

    shortest_completing_word = None

    for word in words:
        word_letter_counts = {}
        for char in word:
            word_letter_counts[char] = word_letter_counts.get(char, 0) + 1

        completes = True
        # Ensure the word has all the letters from the license plate
        for letter, count in license_plate_letter_counts.items():
            if letter not in word_letter_counts or word_letter_counts[letter] < count:
                completes = False
                break

        if completes:
            # Update if current word is shorter
            if shortest_completing_word is None or len(word) < len(shortest_completing_word):
                shortest_completing_word = word

    return shortest_completing_word

Big(O) Analysis

Time Complexity
O(N * M + L * K)Let N be the length of the license plate, M be the average length of a word in the word list, L be the number of words in the word list, and K be the length of the longest word in the word list. Counting letter frequencies in the license plate takes O(N) time. We then iterate through the L words in the word list. For each word, we count letter frequencies, which takes O(M) time. Comparing the letter frequencies of a word to the license plate's frequencies takes O(26) which is constant, and can be considered O(1). Keeping track of the shortest word involves comparing string lengths which is at most O(K). Therefore, the overall time complexity is O(N + L * (M+1) +K), which simplifies to O(N * M + L * K).
Space Complexity
O(1)The algorithm's space complexity is determined primarily by the space used to store the letter counts for both the license plate and each word. Since the English alphabet has a fixed number of characters (26), the space used to store these counts remains constant, irrespective of the length of the license plate or the words in the list. Therefore, the auxiliary space used is constant. This constant space usage leads to an O(1) space complexity.

Edge Cases

licensePlate is null or empty
How to Handle:
Return an empty string or null, as no completing word can be determined.
words array is null or empty
How to Handle:
Return an empty string or null, as there are no words to search within.
One or more words are empty strings
How to Handle:
Treat empty strings as invalid words and skip them in the search.
licensePlate contains only non-alphabetic characters
How to Handle:
Return the shortest word ignoring the license plate completely, essentially finding the shortest word in the words array.
All words do not complete the license plate
How to Handle:
Return an empty string or null, or throw an exception indicating no solution found.
Multiple words complete the license plate with the same minimum length
How to Handle:
Return the first such word encountered to satisfy the 'shortest' requirement while handling ties consistently.
licensePlate contains uppercase and lowercase letters
How to Handle:
Convert the licensePlate to lowercase to perform case-insensitive matching.
Extremely long words array and/or words with large lengths may cause time-out issue
How to Handle:
Consider using a more efficient data structure to store and compare character frequencies.