Shortest Completing Word - Practice Coding Problems

Shortest Completing Word - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: "steps"

💡 Note: The license plate contains letters 's', 'p', 't' (ignoring case and numbers). "step" has s:1, t:1, e:1, p:1 but missing required letters. "steps" has s:2, t:1, e:1, p:1 which covers all requirements. "stripe" and "stepple" are longer, so "steps" is the shortest completing word.

Example 2 — Multiple Same Letters

$ Input: licensePlate = "1s3 333", words = ["S", "sss", "look"]

› Output: "sss"

💡 Note: The license plate contains only 's' (once). "S" has s:1 which satisfies the requirement and is shortest. Wait, let me recalculate: "S" has 1 character, "sss" has 3 characters, so "S" should be shorter and returned first.

Example 3 — Case Sensitivity

$ Input: licensePlate = "Ah71752", words = ["suggest", "letter", "of", "husband", "easy", "education", "drug", "prevent", "writer", "old"]

› Output: "husband"

💡 Note: The license plate contains 'A' and 'h' (case insensitive, so 'a' and 'h'). "husband" contains both 'a' and 'h', and among valid words, it appears first in the array with reasonable length.

Constraints

1 ≤ licensePlate.length ≤ 7
1 ≤ words.length ≤ 1000
1 ≤ words[i].length ≤ 15
licensePlate consists of digits, letters, and spaces
words[i] consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

License plate "1s3 PSt" → letters: s,p,t

Process

Check each word for required letters

Output

Return shortest valid word

Key Takeaway

🎯 Key Insight: Use frequency counting to efficiently match letter requirements between license plate and candidate words

Asked in

A Amazon 25 M Microsoft 18 G Google 15

The key insight is to use frequency counting to efficiently match letter requirements. Extract letters from the license plate, build frequency maps for comparison, and find the shortest word that contains all required letters with correct counts. Best approach uses frequency maps with Time: O(n × m), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Map Approach	O(n × m)	O(k)	Use hash maps to count character frequencies efficiently
Brute Force Character Counting	O(n × m × k)	O(1)	For each word, manually count characters and compare with license plate

Frequency Map Approach — Algorithm Steps

Build frequency map of license plate letters
For each word, build its frequency map
Compare maps to check if word satisfies requirements
Return shortest valid word

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Plate Map

Create frequency map: {s:1, p:1, t:1}

Compare Word Maps

Check if word frequency >= plate frequency

Find Shortest

Return shortest word that passes frequency check

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

char* solution(char* licensePlate, char** words, int wordsSize) {
    // Build frequency map of license plate letters (using array for a-z)
    int plateFreq[26] = {0};
    for (int i = 0; licensePlate[i]; i++) {
        if (isalpha(licensePlate[i])) {
            plateFreq[tolower(licensePlate[i]) - 'a']++;
        }
    }
    
    char* shortestWord = NULL;
    int shortestLength = INT_MAX;
    
    // Check each word
    for (int i = 0; i < wordsSize; i++) {
        char* word = words[i];
        int wordFreq[26] = {0};
        
        // Build frequency map for current word
        for (int j = 0; word[j]; j++) {
            if (isalpha(word[j])) {
                wordFreq[tolower(word[j]) - 'a']++;
            }
        }
        
        // Check if word contains all required letters with correct frequencies
        int isCompleting = 1;
        for (int j = 0; j < 26; j++) {
            if (wordFreq[j] < plateFreq[j]) {
                isCompleting = 0;
                break;
            }
        }
        
        // Update shortest if this word is valid and shorter
        int wordLen = strlen(word);
        if (isCompleting && wordLen < shortestLength) {
            shortestWord = word;
            shortestLength = wordLen;
        }
    }
    
    return shortestWord;
}

int main() {
    char licensePlate[1000];
    fgets(licensePlate, sizeof(licensePlate), stdin);
    licensePlate[strcspn(licensePlate, "\n")] = 0;
    
    char wordsLine[10000];
    fgets(wordsLine, sizeof(wordsLine), stdin);
    wordsLine[strcspn(wordsLine, "\n")] = 0;
    
    // Parse JSON array manually
    char** words = malloc(1000 * sizeof(char*));
    int wordsSize = 0;
    
    char* ptr = wordsLine + 1;
    char word[1000];
    int wordIdx = 0;
    int inQuotes = 0;
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '"') {
            if (inQuotes) {
                word[wordIdx] = '\0';
                words[wordsSize] = malloc(strlen(word) + 1);
                strcpy(words[wordsSize], word);
                wordsSize++;
                wordIdx = 0;
            }
            inQuotes = !inQuotes;
        } else if (inQuotes) {
            word[wordIdx++] = *ptr;
        }
        ptr++;
    }
    
    char* result = solution(licensePlate, words, wordsSize);
    printf("%s\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n words, each taking O(m) time to build frequency map and compare

✓ Linear Growth

Space Complexity

O(k)

k is number of unique characters, space for frequency maps

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Map Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler