Shortest Completing Word: Frequency Counting with Hash Maps

LeetCode 748, Shortest Completing Word, asks you to find the shortest word from a list that contains every letter in a given license plate string. You ignore digits, spaces, and case in the plate. Each letter in the plate must appear at least as many times in the word. If you have solved Valid Anagram or Ransom Note, this problem uses the exact same frequency counting building block.

Let's break it down.

The problem

Given a string licensePlate and an array of strings words, find the shortest word in words that "completes" the license plate. A word completes the plate if it contains every letter in the plate, with frequencies at least as large. Ignore digits, spaces, and treat all letters as lowercase. If there are ties in length, return the first one that appears.

Example: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]. The plate letters are s, p, s, t (lowercased). The word "steps" contains s:2, p:1, t:1, which covers all required letters, and it is the shortest qualifying word.

The question boils down to: which word is the shortest one whose letter frequencies are a superset of the plate's letter frequencies?

Why this problem matters

Frequency counting is one of the most reusable patterns in programming interviews. You build a hash map of counts from one source, then verify that another source meets or exceeds those counts. This same mechanic powers anagram detection, ransom note validation, sliding window substring problems, and more. Shortest Completing Word is a clean, focused application of this pattern with the added twist of filtering non-letter characters from the plate.

The approach

The strategy has two parts:

1. Extract and count. Walk through the license plate, skip anything that is not a letter, lowercase each letter, and build a frequency map of the required characters.
2. Check each word. For every word in the list, build its own frequency map and check whether it covers every required character with enough copies. Track the shortest word that passes.

This is a direct extension of the "supply vs demand" pattern from Ransom Note. The plate defines the demand. Each word is a potential supply. You just need the shortest supply that satisfies all demand.

The solution

def shortest_completing_word(license_plate: str, words: list[str]) -> str:
    req = {}
    for ch in license_plate:
        if ch.isalpha():
            c = ch.lower()
            req[c] = req.get(c, 0) + 1

    result = None
    for word in words:
        freq = {}
        for ch in word:
            freq[ch] = freq.get(ch, 0) + 1

        if all(freq.get(c, 0) >= req[c] for c in req):
            if result is None or len(word) < len(result):
                result = word

    return result

Let's break each piece down:

• Build the required frequency map. Walk through licensePlate, skip non-letter characters with isalpha(), lowercase each letter, and count its frequency. This gives you a dictionary like {"s": 2, "p": 1, "t": 1}.
• Check each candidate word. For every word, build its frequency map the same way. Then verify that every character in the required map has at least as many occurrences in the word's map.
• Track the shortest. If a word passes the frequency check and is shorter than the current best (or is the first match), update the result.
• Return. After processing all words, result holds the shortest completing word.

Step-by-step walkthrough

Let's trace through licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"].

Notice the simplicity. Each word gets its own frequency map, and we compare it against the required frequencies. No sorting, no complicated data structures. Just counting and comparing.

Alternative: Counter approach

Python's Counter makes the comparison even cleaner:

from collections import Counter

def shortest_completing_word(license_plate: str, words: list[str]) -> str:
    req = Counter(c.lower() for c in license_plate if c.isalpha())

    result = None
    for word in words:
        if not (req - Counter(word)):
            if result is None or len(word) < len(result):
                result = word

    return result

When you subtract two Counters, the result only keeps entries with positive counts (characters where the requirement exceeds the supply). If the result is empty, the word covers everything. This is the same trick used in the Ransom Note Counter approach.

Complexity analysis

Where n is the length of the license plate, m is the number of words, and k is the average word length. We do one pass through the plate and one pass through each word.

*O(1) because the character set is bounded at 26 lowercase English letters. The frequency maps never grow beyond 26 entries.

The building blocks

This problem is built from one core building block:

Frequency counter (supply vs demand)

Count how many times each element appears in the "demand" source (the plate), then check whether each "supply" source (each word) meets or exceeds every count. The template:

req = {}
for item in demand:
    req[item] = req.get(item, 0) + 1

for ch in supply:
    freq[ch] = freq.get(ch, 0) + 1

passes = all(freq.get(c, 0) >= req[c] for c in req)

This same building block powers:

• Valid Anagram: exact frequency match (demand equals supply)
• Ransom Note: supply must cover demand (same as this problem, just one word instead of many)
• Find All Anagrams in a String: frequency matching inside a sliding window
• Minimum Window Substring: frequency counting with a shrinking window to find the smallest qualifying range

The difference between these problems is subtle. Valid Anagram checks for exact equality. Ransom Note checks one supply against one demand. Shortest Completing Word checks multiple supplies and picks the shortest. The underlying frequency comparison is identical in all cases.

Edge cases to watch for

• Plate with no letters. If the plate has only digits and spaces, every word trivially completes it. Return the shortest word in the list.
• Tie in length. The problem says to return the first completing word of the shortest length. Process words in order and only update your result when a match is strictly shorter.
• Extra letters in the word. A word can have letters beyond what the plate requires. "steps" has an 'e' that the plate does not need, but that is fine. We only check that the plate's requirements are met.
• Single-character plate. If the plate has one letter like "a", any word containing at least one 'a' qualifies. Return the shortest such word.

From understanding to recall

Shortest Completing Word is rated Easy, and the code is short. But the value is not in this problem alone. It is in the frequency counting pattern that connects this problem to a family of related challenges. The "build a requirement map, then verify against it" flow is the same mechanic you will use in sliding window problems, permutation checks, and substring matching.

Three weeks from now, when you encounter a problem that says "find the smallest window containing all required characters," you want the frequency comparison template to fire automatically. Spaced repetition makes this happen. You practice the pattern at increasing intervals until it becomes muscle memory, not something you re-derive each time.

Related posts

• Valid Anagram - The simplest frequency counting problem: check if two strings have identical character frequencies
• Ransom Note - The same supply-vs-demand frequency check, applied to a single word instead of searching through a list
• Find All Anagrams in a String - Frequency matching inside a sliding window, a harder application of the same counting pattern