Watch 10 video solutions for Shortest Completing Word, a easy level problem involving Array, Hash Table, String. This walkthrough by Hua Hua has 2,462 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"] Output: "steps" Explanation: licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'. "step" contains 't' and 'p', but only contains 1 's'. "steps" contains 't', 'p', and both 's' characters. "stripe" is missing an 's'. "stepple" is missing an 's'. Since "steps" is the only word containing all the letters, that is the answer.
Example 2:
Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"] Output: "pest" Explanation: licensePlate only contains the letter 's'. All the words contain 's', but among these "pest", "stew", and "show" are shortest. The answer is "pest" because it is the word that appears earliest of the 3.
Constraints:
1 <= licensePlate.length <= 7licensePlate contains digits, letters (uppercase or lowercase), or space ' '.1 <= words.length <= 10001 <= words[i].length <= 15words[i] consists of lower case English letters.Problem Overview: You receive a licensePlate string containing letters, digits, and spaces, plus a list of candidate words. The goal is to return the shortest word that contains every letter from the license plate with at least the same frequency, ignoring case and non‑letter characters.
Approach 1: Counting Letters and Validating Words (O(n * m) time, O(1) space)
This approach treats the problem as a frequency matching task. First iterate through licensePlate and build a fixed-size frequency array of 26 characters for required letters. Ignore digits and spaces, and convert everything to lowercase. Then iterate through each word in the list and compute its own frequency count. Compare the word's counts with the required counts. If the word satisfies every letter requirement, it is a valid completing word. Track the shortest valid candidate while scanning. The constant-sized frequency array keeps space complexity at O(1), and the algorithm performs straightforward scans over each word. This solution heavily uses ideas from hash table style frequency counting and basic string processing.
Approach 2: Using Regular Expressions and Sets (O(n * m) time, O(k) space)
This variant builds validation logic using pattern matching instead of explicit frequency arrays. Extract all letters from licensePlate, normalize them to lowercase, and derive constraints that each candidate word must satisfy. Regular expressions with repeated lookaheads can enforce that required letters exist the needed number of times. Each word is then tested against this compiled pattern. A set can help track unique letters when constructing constraints, while repeated characters must still be encoded in the regex pattern. While the asymptotic time complexity remains O(n * m), regex engines introduce additional constant overhead compared to simple counting. This technique may appeal when your environment already relies heavily on pattern matching logic or when you want a compact validation step.
Recommended for interviews: The counting approach is what interviewers typically expect. It demonstrates understanding of frequency counting, efficient iteration, and constant‑space optimization using a fixed 26‑character array. The regex approach works but hides the core algorithmic idea behind pattern matching. Showing the counting solution first proves you can translate the problem into a clear constraint check using basic array operations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Letters and Validating Words | O(n * m) | O(1) | Best general solution. Fast, simple, and interview friendly. |
| Regular Expressions and Sets | O(n * m) | O(k) | Useful when pattern matching tools are preferred or already used in the codebase. |