Shortest Completing Word

Easy

#0702Time: `O(L + N * M * L)` where `L` is the length of `licensePlate`, `N` is the number of words, and `M` is the maximum length of a word. The `O(M * L)` term comes from iterating `M` times (for each character in a word) and performing a list removal which takes `O(L)` time.Space: `O(L)` to store the list of required characters from the `licensePlate` and its temporary copy for each word.

Data structures

Array Hash Table String

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process of checking for character presence. First, we create a list of all required characters from the licensePlate. Then, for each word in the input array, we create a copy of this character list. We iterate through the word's characters, and for each character, we try to remove it from our copied list. If a word successfully empties the list, it means it contains all the required characters. We keep track of the first such word that has the minimum length.

Algorithm

Initialize an empty List<Character> called requiredChars.
Iterate through the licensePlate. For each character, if it's a letter, convert it to lowercase and add it to requiredChars.
Initialize a String variable result to null.
Iterate through each word in the words array.
Create a temporary list tempChars as a copy of requiredChars.
Iterate through the characters of the current word. For each character c, attempt to remove its first occurrence from tempChars.
After iterating through the word, check if tempChars is empty.
If tempChars is empty, the current word is a completing word. Check if result is null or if the current word is shorter than result. If so, update result to the current word.
After checking all words, return result.

Walkthrough

In this method, we first parse the licensePlate to build a list of the letters it contains, ignoring case, numbers, and spaces. For instance, "1s3 PSt" would result in a list ['s', 'p', 's', 't']. Then, we iterate through every word from the words array. For each word, we make a copy of our required characters list. We then iterate through the word's characters, removing them from the copied list one by one. If the list becomes empty, it signifies that the word contains all necessary letters. We then compare its length with the shortest completing word found so far and update if necessary. The first word encountered with the minimum length is our answer.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public String shortestCompletingWord(String licensePlate, String[] words) {6        List<Character> requiredChars = new ArrayList<>();7        for (char c : licensePlate.toLowerCase().toCharArray()) {8            if (Character.isLetter(c)) {9                requiredChars.add(c);10            }11        }12 13        String shortestWord = null;14 15        for (String word : words) {16            List<Character> tempChars = new ArrayList<>(requiredChars);17            for (char c : word.toCharArray()) {18                // Note: remove(Object) is needed to remove the element,19                // not remove(int index) which would treat char as an index.20                tempChars.remove(Character.valueOf(c));21            }22 23            if (tempChars.isEmpty()) {24                if (shortestWord == null || word.length() < shortestWord.length()) {25                    shortestWord = word;26                }27            }28        }29        return shortestWord;30    }31}

Complexity

Time

`O(L + N * M * L)` where `L` is the length of `licensePlate`, `N` is the number of words, and `M` is the maximum length of a word. The `O(M * L)` term comes from iterating `M` times (for each character in a word) and performing a list removal which takes `O(L)` time.

Space

`O(L)` to store the list of required characters from the `licensePlate` and its temporary copy for each word.

Trade-offs

Pros

The logic is a direct translation of the problem's requirements, making it easy to conceptualize.

Cons

Inefficient due to the list.remove(Object) operation inside a loop, which has a linear time complexity with respect to the list size.
Creates a new list object for every word, which can be memory-intensive for a large number of words.

A more efficient method is to use frequency counting. Instead of repeatedly searching and removing characters, we can pre-calculate the frequency of required characters from the licensePlate. We store these counts in an array of size 26 (for each letter 'a' through 'z'). Then, for each word in the words array, we also calculate its character frequency. A word is "completing" if its character counts are greater than or equal to the required counts for all letters. This avoids costly list operations and provides a much faster solution.

Algorithm

Create an integer array plateCounts of size 26, initialized to zeros.
Iterate through the licensePlate. For each character, if it's a letter, convert it to lowercase and increment the corresponding count in plateCounts.
Initialize a String variable result to null.
Iterate through each word in the words array.
Create a temporary integer array wordCounts of size 26 for the current word's character frequencies and populate it.
Compare wordCounts with plateCounts. The word is completing if wordCounts[i] >= plateCounts[i] for all i from 0 to 25.
If the word is completing, check if result is null or if the current word is shorter than result. If so, update result to the current word.
After checking all words, return result.

Walkthrough

This optimized approach hinges on character frequency analysis. First, we create a character frequency map for the licensePlate. Since we only care about lowercase English letters, a simple integer array of size 26 is perfect for this. We iterate through the licensePlate, count the occurrences of each letter, and store them in this array.

Next, we iterate through each word in the words array. For each word, we generate its own frequency array. Then, we compare the word's frequency array with the license plate's frequency array. If for every letter of the alphabet, the count in the word's array is greater than or equal to the count in the license plate's array, the word is a 'completing word'. We keep track of the shortest such word found, ensuring we pick the first one in case of a tie in length.

1class Solution {2    public String shortestCompletingWord(String licensePlate, String[] words) {3        int[] plateCounts = new int[26];4        for (char c : licensePlate.toCharArray()) {5            if (Character.isLetter(c)) {6                plateCounts[Character.toLowerCase(c) - 'a']++;7            }8        }9 10        String result = null;11 12        for (String word : words) {13            int[] wordCounts = new int[26];14            for (char c : word.toCharArray()) {15                wordCounts[c - 'a']++;16            }17 18            boolean isCompleting = true;19            for (int i = 0; i < 26; i++) {20                if (wordCounts[i] < plateCounts[i]) {21                    isCompleting = false;22                    break;23                }24            }25 26            if (isCompleting) {27                if (result == null || word.length() < result.length()) {28                    result = word;29                }30            }31        }32        return result;33    }34}

Complexity

Time

`O(L + N * M)` where `L` is the length of `licensePlate`, `N` is the number of words, and `M` is the maximum length of a word. We spend `O(L)` to process the license plate and `O(M)` for each of the `N` words. The comparison of frequency arrays takes constant time, `O(26)`.

Space

`O(1)` because the space used for the frequency arrays is constant (size 26), regardless of the input size.

Trade-offs

Pros

Highly efficient in both time and space, representing the optimal solution.
Uses a standard and effective pattern for frequency-based string problems.
The fixed-size array is faster and more memory-efficient than a HashMap for this specific problem.

Cons

Slightly more abstract than the direct simulation, but the logic is standard for this type of problem.

Solutions

Solution

1class Solution { public String shortestCompletingWord ( String licensePlate , String [] words ) { int [] cnt = new int [ 26 ]; for ( int i = 0 ; i < licensePlate . length (); ++ i ) { char c = licensePlate . charAt ( i ); if ( Character . isLetter ( c )) { cnt [ Character . toLowerCase ( c ) - 'a' ]++; } } String ans = "" ; for ( String w : words ) { if (! ans . isEmpty () && w . length () >= ans . length ()) { continue ; } int [] t = new int [ 26 ]; for ( int i = 0 ; i < w . length (); ++ i ) { t [ w . charAt ( i ) - 'a' ]++; } boolean ok = true ; for ( int i = 0 ; i < 26 ; ++ i ) { if ( t [ i ] < cnt [ i ]) { ok = false ; break ; } } if ( ok ) { ans = w ; } } return ans ; } }

1class Solution {2public:3  string shortestCompletingWord(string licensePlate, vector<string> &words) {4    int cnt[26]{};5    for (char &c : licensePlate) {6      if (isalpha(c)) {7        ++cnt[tolower(c) - 'a'];8      }9    }10    string ans;11    for (auto &w : words) {12      if (ans.size() && ans.size() <= w.size()) {13        continue;14      }15      int t[26]{};16      for (char &c : w) {17        ++t[c - 'a'];18      }19      bool ok = true;20      for (int i = 0; i < 26; ++i) {21        if (cnt[i] > t[i]) {22          ok = false;23          break;24        }25      }26      if (ok) {27        ans = w;28      }29    }30    return ans;31  }32};

1class Solution:2    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str: cnt = Counter(c . lower() for c in licensePlate if c . isalpha()) ans = None for w in words: if ans and len(w) >= len(ans): continue t = Counter(w) if all(v <= t[c] for c, v in cnt . items()): ans = w return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem