Problem Description

Given a string licensePlate and an array of strings words, you are to find the shortest completing word in words. A completing word is a word that contains all the letters in licensePlate (ignoring case, digits, and spaces), with each letter occurring at least as many times in the word as it appears in licensePlate. You cannot reuse the same letter from licensePlate more than it appears.

• Return the shortest such word from words. If there are multiple, return the first one in the list.
• Assume there is always at least one valid answer.
• Constraints: letters are case-insensitive; ignore non-letter characters in licensePlate.

Thought Process

At first glance, the problem suggests checking every word in words to see if it "completes" the licensePlate. The brute-force way would be to, for each word, count the letters and compare them to the required letters from licensePlate.

However, this can be made more efficient. Instead of repeatedly extracting letters from licensePlate, we can preprocess it once to get a frequency count of its required letters. Then, for each word, we can count its letters and check if it covers all the required counts.

This shifts the problem from repeated string scanning to a more optimized frequency comparison, leveraging hash maps (dictionaries) for fast lookups.

Solution Approach

• Step 1: Preprocess the licensePlate
  • Convert all characters to lowercase for case-insensitive comparison.
  • Filter out non-letter characters (ignore digits and spaces).
  • Count the frequency of each letter using a hash map (or array for 'a'-'z').
• Step 2: Check Each Word in words
  • For each word, count the frequency of its letters (again, case-insensitive).
  • For each letter required by licensePlate, check if the word contains at least as many occurrences.
  • If a word satisfies all required counts, and is shorter than the current best, update the best answer.
• Step 3: Return the Shortest Completing Word
  • Return the shortest word that satisfies the requirement. If multiple words have the same length, return the first one.

Using a hash map or array for letter counts ensures that checking each word is efficient (O(1) per letter), making the overall approach much faster than naive character-by-character matching.

Example Walkthrough

Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]

1. Extract letters from licensePlate:
   • Ignore digits and spaces. Letters are: 's', 'p', 's', 't'
   • Frequency count: {'s':2, 'p':1, 't':1}
2. Check each word:
   • "step": counts {'s':1, 't':1, 'e':1, 'p':1}
     's' only appears once, but need 2. Not a completing word.
   • "steps": counts {'s':2, 't':1, 'e':1, 'p':1}
     All required counts met. Length is 5.
   • "stripe": counts {'s':1, 't':1, 'r':1, 'i':1, 'p':1, 'e':1}
     's' only appears once. Not a completing word.
   • "stepple": counts {'s':1, 't':1, 'e':2, 'p':2, 'l':1}
     's' only once. Not a completing word.
3. Result: "steps" is the shortest completing word.

Time and Space Complexity

• Brute-force Approach:
  • For each word, for each letter in licensePlate, scan the word to count matches.
  • Time: O(N * L * W), where N = number of words, L = length of licensePlate, W = average word length.
• Optimized Approach:
  • Preprocess licensePlate: O(L)
  • For each word, count letters: O(W) per word, O(N * W) total.
  • For each word, compare with license counts: O(1) per letter (since only 26 possible letters).
  • Total Time: O(N * W + L)
  • Space: O(1) extra space for letter counts (since 26 letters), plus input size.

Summary

The key to solving the "Shortest Completing Word" problem efficiently is to preprocess the licensePlate into a frequency table, then use letter counts to quickly check each word. This avoids repeated scanning and leverages fast hash map or array lookups. The solution is both straightforward and efficient, making it a great example of how preprocessing and data structures can simplify string-matching problems.

Code Implementation

from collections import Counter

class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: list) -> str:
        # Prepare frequency count of letters in licensePlate
        license_count = Counter(
            c.lower() for c in licensePlate if c.isalpha()
        )

        answer = None
        for word in words:
            word_count = Counter(word.lower())
            if all(word_count[char] >= license_count[char] for char in license_count):
                if answer is None or len(word) < len(answer):
                    answer = word
        return answer
      

#include <vector>
#include <string>
#include <cctype>
#include <algorithm>
using namespace std;

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        int licenseCount[26] = {0};
        for (char c : licensePlate) {
            if (isalpha(c)) {
                licenseCount[tolower(c) - 'a']++;
            }
        }
        string answer = "";
        for (const string& word : words) {
            int wordCount[26] = {0};
            for (char c : word) {
                wordCount[tolower(c) - 'a']++;
            }
            bool valid = true;
            for (int i = 0; i < 26; ++i) {
                if (licenseCount[i] > wordCount[i]) {
                    valid = false;
                    break;
                }
            }
            if (valid && (answer.empty() || word.length() < answer.length())) {
                answer = word;
            }
        }
        return answer;
    }
};
      

class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] licenseCount = new int[26];
        for (char c : licensePlate.toCharArray()) {
            if (Character.isLetter(c)) {
                licenseCount[Character.toLowerCase(c) - 'a']++;
            }
        }
        String answer = null;
        for (String word : words) {
            int[] wordCount = new int[26];
            for (char c : word.toCharArray()) {
                wordCount[Character.toLowerCase(c) - 'a']++;
            }
            boolean valid = true;
            for (int i = 0; i < 26; i++) {
                if (licenseCount[i] > wordCount[i]) {
                    valid = false;
                    break;
                }
            }
            if (valid && (answer == null || word.length() < answer.length())) {
                answer = word;
            }
        }
        return answer;
    }
}
      

/**
 * @param {string} licensePlate
 * @param {string[]} words
 * @return {string}
 */
var shortestCompletingWord = function(licensePlate, words) {
    const licenseCount = Array(26).fill(0);
    for (let c of licensePlate) {
        if (/[a-zA-Z]/.test(c)) {
            licenseCount[c.toLowerCase().charCodeAt(0) - 97]++;
        }
    }
    let answer = null;
    for (let word of words) {
        const wordCount = Array(26).fill(0);
        for (let c of word) {
            wordCount[c.toLowerCase().charCodeAt(0) - 97]++;
        }
        let valid = true;
        for (let i = 0; i < 26; i++) {
            if (licenseCount[i] > wordCount[i]) {
                valid = false;
                break;
            }
        }
        if (valid && (answer === null || word.length < answer.length)) {
            answer = word;
        }
    }
    return answer;
};