Problem Description

You are given a license plate string licensePlate and an array of strings words. Your task is to find the shortest "completing word" from the words array.

A completing word is defined as a word that contains all the letters from the licensePlate. When checking for a completing word:

• Ignore all numbers and spaces in the licensePlate
• Treat all letters as case-insensitive (uppercase and lowercase are considered the same)
• If a letter appears multiple times in licensePlate, the completing word must contain that letter at least the same number of times

For example, if licensePlate = "aBc 12c":

• After removing numbers and spaces, we have letters: 'a', 'b', 'c', 'c' (note that 'c' appears twice)
• Valid completing words could be "abccdef" (contains a, b, and at least 2 c's), "caaacab" (contains a, b, and at least 2 c's), or "cbca" (contains a, b, and 2 c's)

The function should return the shortest completing word from the words array. If there are multiple completing words with the same shortest length, return the one that appears first in the words array.

The problem guarantees that at least one completing word exists in the input.

Intuition

The key insight is that we need to check if each word contains at least the required frequency of each letter from the license plate. This naturally leads us to think about frequency counting.

First, we need to extract and count the letters from the license plate. Since we only care about letters (not numbers or spaces) and the comparison is case-insensitive, we can convert everything to lowercase and count only alphabetic characters. This gives us a frequency map of required letters.

For each word in our list, we need to verify if it "covers" all the required letters with their frequencies. A word is valid if for every letter in our license plate frequency map, the word contains at least that many occurrences of that letter. This is essentially checking if the word's frequency map is a "superset" of the license plate's frequency map.

To find the shortest completing word, we can iterate through all words and keep track of the shortest valid one found so far. An optimization here is that if we already found a valid word of length n, we can skip checking any word with length ≥ n since we're looking for the shortest one. This pruning helps reduce unnecessary frequency counting operations.

The "first occurrence" requirement for ties is naturally handled by processing the words in order and only updating our answer when we find a strictly shorter valid word (not equal length), ensuring that among words of the same length, the first one encountered is kept.

Solution Approach

We implement the solution using frequency counting with hash tables (Python's Counter).

Step 1: Count letters in license plate

cnt = Counter(c.lower() for c in licensePlate if c.isalpha())

We iterate through each character in licensePlate, converting to lowercase and keeping only alphabetic characters. The Counter creates a frequency map where keys are letters and values are their counts.

Step 2: Process each word

ans = None
for w in words:

Initialize the answer as None and iterate through each word in the words array.

Step 3: Early termination optimization

if ans and len(w) >= len(ans):
    continue

If we already have a valid answer and the current word's length is greater than or equal to the answer's length, skip this word since we're looking for the shortest completing word.

Step 4: Count letters in current word

t = Counter(w)

Create a frequency map for the current word w.

Step 5: Check if word is completing

if all(v <= t[c] for c, v in cnt.items()):
    ans = w

For each letter c with frequency v in the license plate, check if the word contains at least v occurrences of that letter. The expression v <= t[c] verifies this condition. If the word doesn't contain letter c, t[c] returns 0, making the comparison false.

The all() function returns True only if every letter requirement is satisfied. When we find such a word, we update our answer.

Step 6: Return the result

return ans

The algorithm has a time complexity of O(n × m) where n is the number of words and m is the average length of words, since we potentially check each word and count its characters. The space complexity is O(1) for the frequency maps since we only store at most 26 letters.

Example Walkthrough

Let's walk through the solution with licensePlate = "1s3 PSt" and words = ["step", "steps", "stripe", "stepple"].

Step 1: Extract and count letters from license plate

• From "1s3 PSt", we extract only letters: 's', 'P', 'S', 't'
• Convert to lowercase: 's', 'p', 's', 't'
• Count frequencies: cnt = {'s': 2, 'p': 1, 't': 1}

Step 2: Check each word

Word 1: "step"

• Length: 4
• No answer yet, so we proceed
• Count letters: {'s': 1, 't': 1, 'e': 1, 'p': 1}
• Check requirements:
  • Need 's': 2, have 1 ❌ (1 < 2)
  • Since not all requirements are met, skip this word

Word 2: "steps"

• Length: 5
• No answer yet, so we proceed
• Count letters: {'s': 2, 't': 1, 'e': 1, 'p': 1}
• Check requirements:
  • Need 's': 2, have 2 ✓ (2 ≥ 2)
  • Need 'p': 1, have 1 ✓ (1 ≥ 1)
  • Need 't': 1, have 1 ✓ (1 ≥ 1)
• All requirements met! Set ans = "steps"

Word 3: "stripe"

• Length: 6
• We have an answer of length 5, and 6 ≥ 5
• Skip this word (optimization)

Word 4: "stepple"

• Length: 7
• We have an answer of length 5, and 7 ≥ 5
• Skip this word (optimization)

Result: Return "steps" as the shortest completing word.

Note how the optimization allowed us to skip checking the last two words entirely, saving us from unnecessary frequency counting operations.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × m + n × |Σ|) which simplifies to O(n × (m + |Σ|))

The algorithm consists of:

• Creating a counter for the license plate: O(p) where p is the length of licensePlate
• Iterating through each word in words array: O(n) iterations
• For each word:
  • Checking length comparison: O(1)
  • Creating a counter for the word: O(m) where m is the average length of words
  • Checking if all required characters are present: O(|Σ|) where |Σ| = 26 (lowercase letters)

Since we process each word and for each word we perform O(m + |Σ|) operations, the total time complexity is O(n × (m + |Σ|)). When considering that m is typically small and comparable to |Σ|, this can be simplified to O(n × |Σ|) where |Σ| = 26.

Space Complexity: O(|Σ|)

The space usage includes:

• Counter for license plate characters: O(|Σ|) at most 26 unique lowercase letters
• Counter for each word (reused in each iteration): O(|Σ|) at most 26 unique lowercase letters
• Variable to store the answer: O(1)

The dominant space usage is O(|Σ|) where |Σ| = 26 for the character set of lowercase letters.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Case Sensitivity Properly

A frequent mistake is forgetting to convert the license plate letters to lowercase while the words array might contain lowercase letters, or vice versa. This causes valid completing words to be incorrectly rejected.

Incorrect approach:

# Forgetting to normalize case
license_char_count = Counter(char for char in licensePlate if char.isalpha())

Correct approach:

# Convert to lowercase for case-insensitive comparison
license_char_count = Counter(char.lower() for char in licensePlate if char.isalpha())

2. Incorrectly Checking Character Frequencies

Another common error is checking only if the word contains the required letters without verifying the correct frequency. For example, if the license plate has two 'c's, the completing word must have at least two 'c's.

Incorrect approach:

# Only checks if character exists, not the frequency
if all(char in word for char in license_char_count):
    result = word

Correct approach:

# Properly checks that each character appears at least as many times as required
word_char_count = Counter(word)
if all(count <= word_char_count[char] for char, count in license_char_count.items()):
    result = word

3. Not Preserving Order When Multiple Words Have Same Length

When multiple completing words have the same shortest length, the problem requires returning the first one in the array. Using incorrect data structures or sorting can break this requirement.

Incorrect approach:

# Sorting changes the original order
words.sort(key=len)
for word in words:
    # Check completion...

Correct approach:

# Process words in their original order
for word in words:
    if result and len(word) >= len(result):
        continue
    # Check completion...

4. Including Non-Alphabetic Characters in the Count

The problem explicitly states to ignore numbers and spaces, but it's easy to accidentally include them in the character count.

Incorrect approach:

# Counts all characters including digits and spaces
license_char_count = Counter(licensePlate.lower())

Correct approach:

# Filters out non-alphabetic characters
license_char_count = Counter(char.lower() for char in licensePlate if char.isalpha())