Shortest Completing Word

Easy
1779.

Shortest Completing Word

Shortest Completing Word is an easy coding problem on arrays, strings and hash table, asked in Google interviews.

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 <= 7
  • licensePlate holds digits, letters (either case) and spaces
  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 15
  • words[i] holds lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} licensePlate
 * @param {string[]} words
 * @return {string}
 */
var shortestCompletingWord = function(licensePlate, words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 7
  • licensePlate holds digits, letters (either case) and spaces
  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 15
  • words[i] holds lowercase English letters

Hints for Shortest Completing Word

  1. Hint 1

    Reduce the plate to 26 letter counts first — digits, spaces and case all disappear.

  2. Hint 2

    A word completes the plate exactly when its own 26 counts are each at least the plate's.

  3. 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

  1. Count the plate's letters into need[26], lowercasing and skipping everything that is not a letter.
  2. For each word in order, skip it if it is not shorter than the best found so far.
  3. Otherwise count its letters and check count[c] >= need[c] for all 26 letters; if so, it becomes the best.
  4. 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 best

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings