Shortest Completing Word — Solution in Python, Java & C++
Shortest Completing Word solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Google.
Shortest Completing Word is an easy coding problem on arrays, strings and hash table, asked in Google interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Hash Table
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string licensePlate and a list of lowercase words.
Only the letters of licensePlate matter: ignore its digits and spaces, and treat upper- and lowercase letters as the same. A word completes the plate when it contains every one of those letters at least as many times as the plate does (a letter that appears twice on the plate must appear at least twice in the word).
Return the shortest completing word. If several completing words share the shortest length, return the one that appears first in words. An answer is guaranteed to exist.
Example 1
Input: licensePlate = "aB 7b", words = ["bake","abbey","barb","bob"]
Output: barb
Explanation: The plate needs one `a` and two `b`s. `abbey` (5 letters) and `barb` (4 letters) both complete it; `barb` is shorter.
Example 2
Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
Output: pest
Explanation: Only an `s` is needed. Three words of length 4 qualify, and `pest` comes first.
Example 3
Input: licensePlate = "Zz9", words = ["zaz","z","zz"]
Output: zz
Explanation: Case is ignored, so two `z`s are needed and `z` alone is not enough.
Constraints
1 <= licensePlate.length <= 7licensePlate holds digits, letters (either case) and spaces1 <= words.length <= 10001 <= words[i].length <= 15words[i] holds lowercase English letters
Hints for Shortest Completing Word
Hint 1
Reduce the plate to 26 letter counts first — digits, spaces and case all disappear.
Hint 2
A word completes the plate exactly when its own 26 counts are each at least the plate's.
Hint 3
Scan the words in order and replace the current best only on a strictly shorter completing word, so ties keep the earliest.
How to solve Shortest Completing Word
Comparing letter counts rather than letters turns the check into 26 integer comparisons per word. Scanning in order and keeping the best only on a strictly shorter length gives the earliest-of-shortest rule for free.
Approach
- Count the plate's letters into
need[26], lowercasing and skipping everything that is not a letter. - For each word in order, skip it if it is not shorter than the best found so far.
- Otherwise count its letters and check
count[c] >= need[c]for all 26 letters; if so, it becomes the best. - Return the best word.
Why it works
A word contains the plate's letters with multiplicity exactly when every letter's count in the word reaches the plate's count. Because the best only changes on a strictly shorter word, the first of the shortest completing words is never displaced by a later word of the same length.
Complexity
- Time —
O(P + Σ|words[i]|) - Space —
O(1)
Pitfalls
- Uppercase plate letters must count toward the lowercase letter.
- Multiplicity matters: a plate with two
ss rejects a word with one. - Using
<=when comparing lengths returns the last shortest word instead of the first.
Reference solution
Python
from typing import List
def shortestCompletingWord(licensePlate: str, words: List[str]) -> str:
need = [0] * 26
for ch in licensePlate.lower():
if 'a' <= ch <= 'z':
need[ord(ch) - 97] += 1
best = None
for w in words:
if best is not None and len(w) >= len(best):
continue
cnt = [0] * 26
for ch in w:
cnt[ord(ch) - 97] += 1
if all(cnt[i] >= need[i] for i in range(26)):
best = w
return bestJava
public static String shortestCompletingWord(String licensePlate, String[] words) {
int[] need = new int[26];
for (char ch : licensePlate.toCharArray()) {
if (Character.isLetter(ch)) need[Character.toLowerCase(ch) - 'a']++;
}
String best = null;
for (String w : words) {
if (best != null && w.length() >= best.length()) continue;
int[] cnt = new int[26];
for (char ch : w.toCharArray()) cnt[ch - 'a']++;
boolean ok = true;
for (int k = 0; k < 26; k++) if (cnt[k] < need[k]) { ok = false; break; }
if (ok) best = w;
}
return best;
}C++
string shortestCompletingWord(string licensePlate, vector<string>& words) {
int need[26] = {0};
for (char ch : licensePlate) {
if (isalpha((unsigned char)ch)) need[tolower((unsigned char)ch) - 'a']++;
}
int best = -1;
for (int w = 0; w < (int)words.size(); w++) {
if (best >= 0 && words[w].size() >= words[best].size()) continue;
int cnt[26] = {0};
for (char ch : words[w]) cnt[ch - 'a']++;
bool ok = true;
for (int k = 0; k < 26; k++) if (cnt[k] < need[k]) { ok = false; break; }
if (ok) best = w;
}
return words[best];
}JavaScript
var shortestCompletingWord = function(licensePlate, words) {
var need = new Array(26).fill(0);
for (var i = 0; i < licensePlate.length; i++) {
var c = licensePlate.charCodeAt(i);
if (c >= 65 && c <= 90) need[c - 65]++;
else if (c >= 97 && c <= 122) need[c - 97]++;
}
var best = null;
for (var w = 0; w < words.length; w++) {
var word = words[w];
if (best !== null && word.length >= best.length) continue;
var cnt = new Array(26).fill(0);
for (var j = 0; j < word.length; j++) cnt[word.charCodeAt(j) - 97]++;
var ok = true;
for (var k = 0; k < 26; k++) if (cnt[k] < need[k]) { ok = false; break; }
if (ok) best = word;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.