LeetCode 748 - Shortest Completing Word

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String

Solution

Problem Understanding

The problem gives us a string called licensePlate and an array of candidate words called words. We must find the shortest word that satisfies all the letter requirements contained in licensePlate.

The key detail is that only alphabetic characters matter. Digits and spaces should be ignored completely. In addition, uppercase and lowercase letters are treated as the same character. This means we should normalize all letters to lowercase before processing.

A word is considered a "completing word" if it contains every required letter from licensePlate, including duplicates. For example, if the license plate contains the letter 's' twice, then the candidate word must also contain at least two 's' characters.

The input size is relatively small:

licensePlate.length <= 7
words.length <= 1000
words[i].length <= 15

These constraints tell us that we do not need highly advanced optimization techniques. A direct frequency counting approach will easily fit within the limits.

The output should be the shortest completing word. If multiple words have the same minimum length, we must return the first one that appears in the input list. This means the order of iteration matters.

Several edge cases are important:

The license plate may contain no useful characters except one letter.
Letters may repeat multiple times.
Uppercase and lowercase letters must be treated identically.
Multiple candidate words may have the same valid shortest length.
The answer is guaranteed to exist, so we do not need to handle failure cases.

Approaches

Brute Force Approach

A brute force solution would process every word independently and repeatedly scan it for every required character in the license plate.

One naive implementation could work like this:

Extract all letters from licensePlate.
For each word:

For each required character:
Count how many times it appears in the word.
Compare against the required frequency.

Track the shortest valid word.

This approach is correct because every candidate word is explicitly checked against the requirements. However, it performs repeated scans of the same word for each required letter, which is inefficient.

For example, if the license plate requires multiple different characters, the same word may be scanned many times to compute frequencies repeatedly.

Optimal Approach

The key observation is that character frequencies can be precomputed efficiently.

Instead of repeatedly scanning words, we can:

Build a frequency array for the license plate.
For each candidate word:

Build its own frequency array once.
Compare the two arrays.

Select the shortest valid word.

Since there are only 26 lowercase English letters, comparing frequency arrays is very cheap and effectively constant time.

This approach avoids redundant counting work and leads to a clean and efficient implementation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(W × L × R)	O(1)	Repeatedly scans words for each required letter
Optimal	O(W × L)	O(1)	Uses frequency counting for efficient validation

Where:

W = number of words
L = average word length
R = number of required letters in the license plate

Because the alphabet size is fixed at 26, the extra memory usage is constant.

Algorithm Walkthrough

Create a frequency array of size 26 for the license plate requirements.

Each index represents a lowercase letter from 'a' to 'z'. For every alphabetic character in licensePlate, convert it to lowercase and increment its corresponding count.

This array stores exactly how many times each letter is required. 2. Initialize a variable to store the current best answer.

Initially, no answer has been chosen yet. 3. Iterate through every word in words.

Since ties must return the earliest word, we process words in their original order. 4. Build a frequency array for the current word.

Count how many times each letter appears in the word. 5. Compare the word frequency against the required frequency.

For every letter from 'a' to 'z', verify that:

word_count[i] >= required_count[i]

If any required letter is missing or insufficient, the word is invalid. 6. If the word is valid, compare its length with the current best answer.

Update the answer if:

no answer exists yet, or
the current word is shorter

We do not update on equal length because the earlier word should remain the answer. 7. After processing all words, return the stored answer.

Why it works

The algorithm works because every candidate word is checked against the exact frequency requirements extracted from the license plate. A word is accepted only if it contains every required character with sufficient multiplicity. Since we process words in order and only replace the answer when a strictly shorter word is found, the final result is guaranteed to be the earliest shortest completing word.

Python Solution

from typing import List

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

        for char in licensePlate:
            if char.isalpha():
                index = ord(char.lower()) - ord('a')
                required[index] += 1

        answer = ""

        for word in words:
            counts = [0] * 26

            for char in word:
                counts[ord(char) - ord('a')] += 1

            is_valid = True

            for i in range(26):
                if counts[i] < required[i]:
                    is_valid = False
                    break

            if is_valid:
                if answer == "" or len(word) < len(answer):
                    answer = word

        return answer

The implementation begins by constructing the required frequency array from the license plate. Only alphabetic characters are processed, and each character is converted to lowercase to ensure case insensitivity.

For every candidate word, another frequency array called counts is built. This allows constant time access to the frequency of any letter.

The validation loop checks whether the word satisfies all required counts. If any character frequency is insufficient, the word is rejected immediately.

When a valid word is found, the algorithm updates the answer only if the new word is strictly shorter. This preserves the first occurrence rule for ties.

Finally, the shortest valid word is returned.

Go Solution

func shortestCompletingWord(licensePlate string, words []string) string {
	required := make([]int, 26)

	for _, ch := range licensePlate {
		if ch >= 'a' && ch <= 'z' {
			required[ch-'a']++
		} else if ch >= 'A' && ch <= 'Z' {
			required[ch-'A']++
		}
	}

	answer := ""

	for _, word := range words {
		counts := make([]int, 26)

		for _, ch := range word {
			counts[ch-'a']++
		}

		valid := true

		for i := 0; i < 26; i++ {
			if counts[i] < required[i] {
				valid = false
				break
			}
		}

		if valid {
			if answer == "" || len(word) < len(answer) {
				answer = word
			}
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version. One small difference is that Go does not provide built in case normalization as conveniently as Python, so uppercase and lowercase checks are handled explicitly during license plate processing.

Slices are used for the frequency arrays, and since the alphabet size is fixed at 26, memory usage remains constant.

There are no integer overflow concerns because all counts are very small under the given constraints.

Worked Examples

Example 1

Input:

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

Step 1: Build Required Frequency

Relevant letters:

s, p, s, t

Frequency table:

Letter	Count
s	2
p	1
t	1

Step 2: Check Each Word

Word: `"step"`

Frequency table:

Letter	Count
s	1
t	1
e	1
p	1

Requirement check:

Letter	Required	Present	Valid
s	2	1	No
p	1	1	Yes
t	1	1	Yes

Result: Invalid

Word: `"steps"`

Frequency table:

Letter	Count
s	2
t	1
e	1
p	1

Requirement check:

Letter	Required	Present	Valid
s	2	2	Yes
p	1	1	Yes
t	1	1	Yes

Result: Valid

Current answer:

"steps"

Word: `"stripe"`

Letter	Required	Present	Valid
s	2	1	No

Result: Invalid

Word: `"stepple"`

Letter	Required	Present	Valid
s	2	1	No

Result: Invalid

Final answer:

"steps"

Example 2

Input:

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

Step 1: Build Required Frequency

Relevant letters:

Frequency table:

Letter	Count
s	1

Step 2: Check Words

Word	Contains 's'?	Length	Current Best
looks	Yes	5	looks
pest	Yes	4	pest
stew	Yes	4	pest
show	Yes	4	pest

The tie between "pest", "stew", and "show" is resolved by input order.

Final answer:

"pest"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(W × L)	Each word is scanned once to build frequencies
Space	O(1)	Frequency arrays always have fixed size 26

The algorithm processes every character in every word exactly once. The additional comparison over 26 letters is constant time because the alphabet size never changes.

The memory usage is constant because both frequency arrays always contain exactly 26 integers regardless of input size.

Test Cases

from typing import List

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

        for char in licensePlate:
            if char.isalpha():
                required[ord(char.lower()) - ord('a')] += 1

        answer = ""

        for word in words:
            counts = [0] * 26

            for char in word:
                counts[ord(char) - ord('a')] += 1

            valid = True

            for i in range(26):
                if counts[i] < required[i]:
                    valid = False
                    break

            if valid:
                if answer == "" or len(word) < len(answer):
                    answer = word

        return answer

solution = Solution()

assert solution.shortestCompletingWord(
    "1s3 PSt",
    ["step", "steps", "stripe", "stepple"]
) == "steps"  # repeated letter requirement

assert solution.shortestCompletingWord(
    "1s3 456",
    ["looks", "pest", "stew", "show"]
) == "pest"  # tie resolved by earliest occurrence

assert solution.shortestCompletingWord(
    "Ah71752",
    ["suggest", "letter", "of", "husband", "easy", "education", "drug", "prevent", "writer", "old"]
) == "husband"  # mixed uppercase and lowercase

assert solution.shortestCompletingWord(
    "OgEu755",
    ["enough", "these", "play", "wide", "wonder", "box", "arrive", "money", "tax", "thus"]
) == "enough"  # multiple required letters

assert solution.shortestCompletingWord(
    "aA",
    ["a", "aa", "aaa"]
) == "aa"  # duplicate character requirement

assert solution.shortestCompletingWord(
    "Z",
    ["zz", "z", "zzz"]
) == "z"  # shortest valid word

assert solution.shortestCompletingWord(
    "1 2 3 a",
    ["bbb", "caa", "abcd"]
) == "caa"  # ignores digits and spaces

assert solution.shortestCompletingWord(
    "pp",
    ["p", "pp", "ppp"]
) == "pp"  # exact frequency match

assert solution.shortestCompletingWord(
    "t",
    ["to", "tea", "ted"]
) == "to"  # earliest among equal shortest lengths

Test	Why
`"1s3 PSt"`	Verifies repeated letters are enforced
`"1s3 456"`	Verifies earliest tie breaking
`"Ah71752"`	Verifies case insensitive processing
`"OgEu755"`	Verifies multiple required letters
`"aA"`	Verifies duplicate counts are preserved
`"Z"`	Verifies single character matching
`"1 2 3 a"`	Verifies digits and spaces are ignored
`"pp"`	Verifies exact repeated frequency handling
`"t"`	Verifies stable ordering for equal lengths

Edge Cases

One important edge case occurs when the license plate contains repeated letters. For example, "aA" requires two occurrences of the letter 'a', not just one. A naive implementation using sets instead of frequency counts would incorrectly accept words containing only one 'a'. The frequency array approach handles this correctly by storing exact counts.

Another critical edge case involves uppercase letters. The problem explicitly states that matching should be case insensitive. Without normalization, characters like 'S' and 's' would be treated differently. The implementation converts all license plate letters to lowercase before counting, ensuring consistent matching behavior.

A third important edge case is tie resolution. Multiple words may have the same shortest valid length. The problem requires returning the earliest occurrence in the input array. The implementation preserves this behavior by updating the answer only when a strictly shorter word is found. Equal length words do not replace the current answer.

A final edge case involves license plates containing mostly digits and spaces. For example, "1 2 3 a" only requires the letter 'a'. A buggy implementation might accidentally process digits as characters or fail when few letters are present. The algorithm explicitly checks isalpha() in Python and letter ranges in Go, ensuring that only alphabetic characters affect the requirements.

LeetCode 748 - Shortest Completing Word

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Step 1: Build Required Frequency

Step 2: Check Each Word

Word: "step"

Word: "steps"

Word: "stripe"

Word: "stepple"

Example 2

Step 1: Build Required Frequency

Step 2: Check Words

Complexity Analysis

Test Cases

Edge Cases

Word: `"step"`

Word: `"steps"`

Word: `"stripe"`

Word: `"stepple"`