748. Shortest Completing Word

EasyArrayHash TableString
Leetcode Link

Problem Description

In this LeetCode problem, we are given a string licensePlate and an array of strings words. Our task is to find the shortest word in words that contains all the letters in licensePlate, disregarding any numbers and spaces, and treating letters as case-insensitive. Notably, if a letter repeats in the licensePlate, it must appear at least as many times in the word. The essence of the problem is to identify the most concise word from an array that encapsulates all alphabetic characters of the given license plate string.

Intuition

To arrive at the solution for this problem, we breakdown the requirements into smaller steps and handle each part. First, we create a function called count that converts a given word into a frequency array that represents how many times each letter appears in the word.

Once we have count, we need a way to determine if a word in words can be considered a "completing word". To do this, we craft a check function that compares two frequency arrays: one from the cleaned licensePlate and one from a candidate word. The check function goes over each letter's frequency and ensures the candidate word has equal or more occurrences of each letter found in licensePlate.

Then we iterate over each word in words and apply the count function to it. If it passes the check with the licensePlate's frequency array, it means we've found a potential completing word. We maintain a variable for the shortest word found (ans) and its length (n). If a new completing word is shorter than the current best, we update ans with this new word.

This way, by prioritizing words that meet the completing criteria and are shorter than any others we've seen, we can solve the problem effectively.

Solution Approach

The solution approach for finding the shortest completing word involves the use of frequency arrays and efficient checks for each word in the words array against the licensePlate. Here's a step-by-step explanation of the implementation:

The count function

We define a count function that takes a word and transforms it into a frequency array, which is an array of 26 integers (corresponding to the 26 letters of the English alphabet), each element representing the count of a specific letter from 'a' to 'z'. The ord function is used to get the ASCII value of a character, and we subtract the ASCII value of 'a' to map 'a' to index 0, 'b' to index 1, and so on up to 'z'.

1def count(word):
2    counter = [0] * 26
3    for c in word:
4        counter[ord(c) - ord('a')] += 1
5    return counter

The check function

The check function compares two frequency arrays: one from the license plate (counter1) and the other from the current word (counter2). If for any letter the count in the license plate is greater than the count in the word, check returns False indicating that the word is not a completing word. Otherwise, if all letter counts are equal or higher in the word than in the license plate, it returns True.

1def check(counter1, counter2):
2    for i in range(26):
3        if counter1[i] > counter2[i]:
4            return False
5    return True

The main loop

The main part of the algorithm is a loop through each word in words. It initializes two variables: ans, to store the currently found shortest completing word, and n, to store its length.

1counter = count(c.lower() for c in licensePlate if c.isalpha())
2ans, n = None, 16
3for word in words:
4    if n <= len(word):
5        continue
6    t = count(word)
7    if check(counter, t):
8        n = len(word)
9        ans = word

The process for each word in the loop is as follows:

  1. We skip the word if its length is not less than the current shortest completing word's length (n) to optimize performance.
  2. We generate a frequency array of the word (t) using count.
  3. We use check to see if t meets the requirements compared to counter, which is the frequency array for licensePlate.
  4. If it does, this is the new shortest completing word, and we update ans with this word and n with its length.

The loop proceeds until all words have been checked, and the shortest completing word (ans) is returned as the answer.

This algorithm effectively leverages data structures (arrays) and functions to compare character frequencies, significantly simplifying and optimizing the process of determining completing words.

💪
Level Up Your
Algo Skills

Example Walkthrough

To illustrate the solution approach, let's take a small example. Suppose licensePlate is "aBc 1123" and words is ["step", "steps", "stripe", "stepple"].

The first step would be to create a frequency array for the cleaned licensePlate, which disregards numbers and spaces and is case-insensitive. This means "aBc" becomes "abc" and our count function generates an array [1, 1, 1, 0, ..., 0], indicating that there's one 'a', one 'b', and one 'c'.

Iterating Over Each Word

We then iterate over each word in words and check if it's a completing word for licensePlate.

  • For "step", we get the frequency array [0, 0, 0, 0, 1, 0, ..., 1], which has an 'e' and a 'p', but lacks 'a' and 'b'.
  • For "steps", the frequency array is [0, 0, 0, 0, 1, 0, ..., 1, 1]. This word also covers 's', but still misses 'a' and 'b'.
  • "stripe" has a frequency array [0, 0, 0, 0, 1, 0, ..., 1, 1, 1], containing 'e', 'p', 'r', 's', 't', and 'i', and it does have at least one 'a', 'b', and 'c'.
  • Finally, "stepple" has the array [0, 0, 0, 0, 1, 0, ..., 2, 2, 1], where there is more than one occurrence of some letters, but it's longer than "stripe".

Through our check function, we see that only "stripe" has equal or more occurrences of the letters in licensePlate, which are 'a', 'b', and 'c', so it is a potential completing word.

Finding the Shortest Completing Word

Since "stripe" is shorter than "stepple" and it contains all the required letters (ignoring the unnecessary 'i', 'r', and 't'), "stripe" becomes our ans and its length, 6, becomes n.

As no other word in words is both a completing word for "aBc 1123" and shorter than "stripe", "stripe" is the answer we return. It successfully encapsulates all alphabetic characters of the license plate "aBc 1123" in the most concise form found in the list words.

This example demonstrates how the count and check functions, together with an iterating loop, can be used to efficiently solve the problem.

Python Solution

1class Solution:
2    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
3      
4        # Helper function to count the frequency of each letter in a word.
5        def count_letters(word):
6            # Initialize a counter for 26 letters of the alphabet.
7            counter = [0] * 26
8            # Increment the letter's corresponding counter.
9            for char in word:
10                counter[ord(char) - ord('a')] += 1
11            return counter
12      
13        # Helper function to check if the word contains all the 
14        # needed letters with required frequency.
15        def contains_needed_letters(license_counter, word_counter):
16            # Iterate through each letter in the alphabet.
17            for i in range(26):
18                # If the license has more letters than the word,
19                # then it's not a completing word.
20                if license_counter[i] > word_counter[i]:
21                    return False
22            return True
23      
24        # Transforms the license plate into lowercase and filters out non-alphabetic characters.
25        # Then, counts the frequency of each letter in the license plate.
26        license_counter = count_letters(char.lower() for char in licensePlate if char.isalpha())
27      
28        # Initialize the variables for tracking the shortest completing word.
29        shortest_completing_word = None
30        min_length = 16 # Given constraint - words length doesn't exceed 15.
31      
32        # Iterate through the words list to find the shortest completing word.
33        for word in words:
34            # Skip the iteration if the current word is not shorter than min_length.
35            if min_length <= len(word):
36                continue
37            # Count the frequency of letters in the current word.
38            word_counter = count_letters(word)
39            # Check if the current word has all the required letters
40            # with at least the frequencies in the license plate.
41            if contains_needed_letters(license_counter, word_counter):
42                # Update min_length and shortest_completing_word with the current word's length and the word itself.
43                min_length = len(word)
44                shortest_completing_word = word
45      
46        return shortest_completing_word
47

Java Solution

1class Solution {
2    // Finds the shortest completing word in words that covers all letters in licensePlate
3    public String shortestCompletingWord(String licensePlate, String[] words) {
4        // Count the frequency of letters in the license plate, ignoring case and non-letters
5        int[] licensePlateCounter = countLetters(licensePlate.toLowerCase());
6      
7        // Initialize the answer variable to hold the shortest completing word
8        String shortestCompletingWord = null;
9      
10        // Initialize the shortest length found so far to an upper bound
11        int minLength = 16; // As per the problem, words are at most 15 letters long
12      
13        // Iterate through each word in the array
14        for (String word : words) {
15            // Skip the word if its length is not less than the shortest length found so far
16            if (minLength <= word.length()) {
17                continue;
18            }
19          
20            // Count the frequency of letters in the current word
21            int[] wordCounter = countLetters(word);
22          
23            // Check if the current word covers all letters in the license plate
24            if (doesWordCoverLicensePlate(licensePlateCounter, wordCounter)) {
25                // Update the shortest completing word and the minimum length found so far
26                minLength = word.length();
27                shortestCompletingWord = word;
28            }
29        }
30      
31        // Return the shortest completing word found
32        return shortestCompletingWord;
33    }
34
35    // Counts the frequency of each letter in a given word
36    private int[] countLetters(String word) {
37        int[] letterCounter = new int[26];
38        // Iterate through each character in the word
39        for (char c : word.toCharArray()) {
40            // Increment the counter for the letter if it's a letter
41            if (Character.isLetter(c)) {
42                letterCounter[c - 'a']++;
43            }
44        }
45        return letterCounter;
46    }
47
48    // Checks if wordCounter covers all the letters in licensePlateCounter
49    private boolean doesWordCoverLicensePlate(int[] licensePlateCounter, int[] wordCounter) {
50        // Iterate over each letter count
51        for (int i = 0; i < 26; ++i) {
52            // If the current letter's count in licensePlateCounter exceeds that in wordCounter,
53            // the word does not cover the license plate, return false
54            if (licensePlateCounter[i] > wordCounter[i]) {
55                return false;
56            }
57        }
58        // If all letter counts are covered, return true
59        return true;
60    }
61}
62

C++ Solution

1#include <string>
2#include <vector>
3#include <cctype> // For isalpha and tolower
4
5class Solution {
6public:
7    // Finds the shortest word in 'words' that contains all the letters in 'licensePlate'
8    string shortestCompletingWord(string licensePlate, vector<string>& words) {
9        // Count the frequency of each letter in the license plate
10        vector<int> licenseCounter = countLetters(licensePlate);
11        int minLength = INT_MAX;
12        string shortestWord;
13
14        // Iterate over each word in the list
15        for (auto& word : words) {
16            // If current word is longer than the shortest found, skip it
17            if (minLength <= word.size()) continue;
18
19            // Count the frequency of each letter in the word
20            vector<int> wordCounter = countLetters(word);
21
22            // Check if the word contains all letters in the license plate
23            if (containsAllLetters(licenseCounter, wordCounter)) {
24                // Update minimum length and answer if this word is shorter
25                minLength = word.size();
26                shortestWord = word;
27            }
28        }
29        return shortestWord;
30    }
31
32private:
33    // Counts the frequency of each letter in a word
34    vector<int> countLetters(string& word) {
35        vector<int> counter(26, 0); // Initiate a counter for 26 letters
36
37        // Increment the count for each letter in the word
38        for (char& c : word) {
39            if (isalpha(c)) {
40                ++counter[tolower(c) - 'a'];
41            }
42        }
43        return counter;
44    }
45
46    // Checks if 'counterSource' contains at least as many of each letter as 'counterTarget'
47    bool containsAllLetters(vector<int>& counterSource, vector<int>& counterTarget) {
48        for (int i = 0; i < 26; ++i) {
49            // If the target has more of a letter than the source, return false
50            if (counterSource[i] > counterTarget[i]) {
51                return false;
52            }
53        }
54        // If the source contains at least as many of each letter, return true
55        return true;
56    }
57};
58

Typescript Solution

1function shortestCompletingWord(licensePlate: string, words: string[]): string {
2  // Count the frequency of each letter in the license plate
3  const licenseCounter: number[] = countLetters(licensePlate);
4  let minLength: number = Number.MAX_SAFE_INTEGER;
5  let shortestWord: string = '';
6
7  // Iterate over each word in the list
8  for (let word of words) {
9    // If the current word is longer than the shortest so far, skip it
10    if (minLength <= word.length) continue;
11  
12    // Count the frequency of each letter in the current word
13    const wordCounter: number[] = countLetters(word);
14
15    // Check if the word contains all the letters in the license plate
16    if (containsAllLetters(licenseCounter, wordCounter)) {
17      // Update minimum length and shortest word if this word is shorter
18      minLength = word.length;
19      shortestWord = word;
20    }
21  }
22  return shortestWord;
23}
24
25// Helper function to count the frequency of each letter in a word
26function countLetters(word: string): number[] {
27  const counter: number[] = new Array(26).fill(0); // Initialize a counter for 26 letters
28
29  // Increment the count for each alphabet letter in the word
30  for (let char of word) {
31    if (isAlphabetic(char)) {
32      counter[char.toLowerCase().charCodeAt(0) - 'a'.charCodeAt(0)]++;
33    }
34  }
35  return counter;
36}
37
38// Helper function to verify if sourceCounter contains at least
39// as many of each letter as targetCounter
40function containsAllLetters(sourceCounter: number[], targetCounter: number[]): boolean {
41  for (let i = 0; i < 26; ++i) {
42    // If the target has more of any particular letter than the source, return false
43    if (sourceCounter[i] < targetCounter[i]) {
44      return false;
45    }
46  }
47  // If source contains at least as many of each letter, return true
48  return true;
49}
50
51// Helper function to check if a character is an alphabetic letter
52function isAlphabetic(char: string): boolean {
53  const code: number = char.charCodeAt(0);
54  return (code >= 65 && code <= 90) || (code >= 97 && code <= 122); // A-Z or a-z
55}
56

Time and Space Complexity

The time complexity of the shortestCompletingWord function primarily depends on two factors: the number of words in the input words list and the average length of each word. Here is the breakdown:

  • The count function has a time complexity of O(k) where k is the length of the word. It iterates once through all the characters of the word.
  • This count function is called for every character in the normalized licensePlate once, resulting in a time complexity of O(m) where m is the number of alphabetic characters in licensePlate.
  • For each word in words, the count function is called again, giving a time complexity of O(k * n) where n is the number of words and k is the average length of the words.
  • The function check has a time complexity of O(1) because it checks a fixed size array (26 letters of English alphabet).
  • Since check is called for every word, we multiply it by n, but it doesn't affect the overall time complexity significantly due to the constant size.

Combining the above steps, the total time complexity for the function is O(m + k * n).

The space complexity is determined by:

  • The counter arrays used to store character frequencies for the licensePlate and each word. Since these are of fixed size (26), they occupy O(1) space.
  • The space used to store the answer and the length of the shortest word found so far (n and ans) is O(1).

Thus, the overall space complexity is O(1) because it does not scale with the size of the input.

In summary:

  • Time Complexity: O(m + k * n)
  • Space Complexity: O(1)
😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫