LeetCode 748: Shortest Completing Word

Problem Restatement

We are given a string licensePlate and a list of words.

A word is called a completing word if it contains every letter from licensePlate.

When reading licensePlate:

• Ignore digits.
• Ignore spaces.
• Treat uppercase and lowercase letters as the same.
• If a letter appears multiple times, the word must contain it at least that many times.

We need to return the shortest completing word from words.

If there are multiple shortest completing words, return the one that appears first in words. The problem guarantees that an answer exists.

Input and Output

Example function shape:

def shortestCompletingWord(
    licensePlate: str,
    words: list[str],
) -> str:
    ...

Examples

Example 1

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

After removing digits and spaces, and converting to lowercase, the required letters are:

s, p, s, t

So the required counts are:

Check the words:

The answer is:

"steps"

Example 2

licensePlate = "1s3 456"
words = ["looks", "pest", "stew", "show"]

The required letters are:

s

The shortest words containing s are "pest" and "stew".

Both have length 4, but "pest" appears first.

The answer is:

"pest"

First Thought: Compare Each Word

We can preprocess the license plate once.

For each word, count its letters and check whether it contains enough of every required letter.

Because there are only 26 lowercase English letters, this comparison is small and simple.

Key Insight

This is a frequency counting problem.

Build a required count array:

need[letter]

Then for each candidate word, build:

have[letter]

The word is completing if for every letter:

have[letter] >= need[letter]

To preserve the tie rule, scan words in order and update the answer only when the valid word is strictly shorter than the current answer.

Algorithm

1. Create an array need of size 26.
2. For each character in licensePlate:
   • If it is a letter, convert it to lowercase.
   • Increment its count in need.
3. Initialize answer = None.
4. For each word in words:
   • If answer exists and len(word) >= len(answer), skip it.
   • Count letters in word.
   • If the word satisfies all required counts, set answer = word.
5. Return answer.

Correctness

The need array records exactly the letters required by the license plate, ignoring digits and spaces and treating letters case-insensitively.

For each word, the algorithm counts its letters and compares those counts with need. A word is accepted only if every required letter appears at least as many times as needed. This matches the definition of a completing word.

The algorithm scans words from left to right. It updates the answer only when it finds a completing word with strictly smaller length. Therefore, when two completing words have the same shortest length, the earlier one remains selected.

Since the problem guarantees that at least one completing word exists, the final answer is the shortest completing word with the required tie behavior.

Complexity

Let n = len(words) and let L be the maximum word length.

The output string itself is not counted as extra working space.

Implementation

class Solution:
    def shortestCompletingWord(
        self,
        licensePlate: str,
        words: list[str],
    ) -> str:
        need = [0] * 26

        for ch in licensePlate:
            if ch.isalpha():
                index = ord(ch.lower()) - ord("a")
                need[index] += 1

        answer = None

        for word in words:
            if answer is not None and len(word) >= len(answer):
                continue

            have = [0] * 26

            for ch in word:
                index = ord(ch) - ord("a")
                have[index] += 1

            ok = True

            for i in range(26):
                if have[i] < need[i]:
                    ok = False
                    break

            if ok:
                answer = word

        return answer

Code Explanation

The required letter counts are stored here:

need = [0] * 26

For every character in the license plate, we only keep letters:

if ch.isalpha():

Then we convert to lowercase and count it:

index = ord(ch.lower()) - ord("a")
need[index] += 1

For each word, we can skip it if it cannot improve the current answer:

if answer is not None and len(word) >= len(answer):
    continue

This keeps the first word when there is a tie.

Then we count the word letters:

have = [0] * 26

for ch in word:
    index = ord(ch) - ord("a")
    have[index] += 1

Finally, compare the two arrays:

for i in range(26):
    if have[i] < need[i]:
        ok = False
        break

If every required count is satisfied, this word becomes the best answer so far.

Testing

def run_tests():
    s = Solution()

    assert s.shortestCompletingWord(
        "1s3 PSt",
        ["step", "steps", "stripe", "stepple"],
    ) == "steps"

    assert s.shortestCompletingWord(
        "1s3 456",
        ["looks", "pest", "stew", "show"],
    ) == "pest"

    assert s.shortestCompletingWord(
        "Ah71752",
        ["suggest", "letter", "of", "husband", "easy", "education", "drug"],
    ) == "husband"

    assert s.shortestCompletingWord(
        "OgEu755",
        ["enough", "these", "play", "wide", "wonder", "box", "arrive", "money", "tax", "thus"],
    ) == "enough"

    assert s.shortestCompletingWord(
        "aBc 12c",
        ["abccdef", "cbca", "caaacab"],
    ) == "cbca"

    print("all tests passed")

run_tests()