Number of Valid Words for Each Puzzle - Solution & Explanation
Problem Statement
puzzle string, a word is valid if both the following conditions are satisfied:
wordcontains the first letter ofpuzzle.- For each letter in
word, that letter is inpuzzle.- For example, if the puzzle is
"abcdefg", then valid words are"faced","cabbage", and"baggage", while - invalid words are
"beefed"(does not include'a') and"based"(includes's'which is not in the puzzle).
- For example, if the puzzle is
answer, where answer[i] is the number of words in the given word list words that is valid with respect to the puzzle puzzles[i].
Example 1:
Input: words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"] Output: [1,1,3,2,4,0] Explanation: 1 valid word for "aboveyz" : "aaaa" 1 valid word for "abrodyz" : "aaaa" 3 valid words for "abslute" : "aaaa", "asas", "able" 2 valid words for "absoryz" : "aaaa", "asas" 4 valid words for "actresz" : "aaaa", "asas", "actt", "access" There are no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.
Example 2:
Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"] Output: [0,1,3,2,0]
Constraints:
1 <= words.length <= 1054 <= words[i].length <= 501 <= puzzles.length <= 104puzzles[i].length == 7words[i]andpuzzles[i]consist of lowercase English letters.- Each
puzzles[i]does not contain repeated characters.
Approach Overview
Problem Overview: You receive a list of words and a list of 7‑letter puzzles. A word is valid for a puzzle if it contains the puzzle’s first letter and every character in the word appears in the puzzle. For each puzzle, return the number of valid words.
Approach 1: Brute Force Approach (O(W * P * L) time, O(1) space)
The most direct strategy checks every word against every puzzle. For each pair, verify two conditions: the word contains the puzzle’s first character, and every letter in the word exists in the puzzle. This can be implemented with sets or frequency arrays. The method is simple but expensive because you repeatedly scan words and puzzles, leading to roughly O(W * P * L) time where L is average word length. Works only for small datasets and mainly helps understand the constraints before optimizing.
Approach 2: Direct Check with Early Stopping (O(W * P) average, O(1) space)
Instead of building sets every time, convert each puzzle into a quick lookup structure such as a boolean array of size 26. While scanning a word, stop immediately if you encounter a character not in the puzzle. Also check early whether the word contains the required first letter. This reduces unnecessary work and improves practical performance, though the theoretical complexity is still close to O(W * P). Useful when implementing a straightforward optimized baseline before introducing bit manipulation.
Approach 3: Bitmask Approach (O(W * P) time, O(W) space)
Represent each word and puzzle as a 26‑bit integer mask where each bit indicates whether a letter exists. Bit operations make subset checks extremely fast. A word is valid if its mask contains the puzzle’s first letter and (wordMask & puzzleMask) == wordMask. This removes character-by-character checks and replaces them with constant-time bit operations. The technique relies heavily on bitmasking and counting masks using a hash table.
Approach 4: Bitmasking with Precomputation (O(W + P * 2^6) time, O(W) space)
The optimal solution precomputes frequencies of word masks using a hash map. Words with more than 7 unique letters can be ignored since puzzles only contain 7 characters. For each puzzle, fix the first letter and generate all subsets of the remaining six letters (there are 2^6 = 64). Combine each subset with the first letter to form candidate masks and look them up in the map. Summing their frequencies gives the valid word count for that puzzle. This dramatically reduces work and runs in roughly O(W + P * 64). Some implementations also use a trie for similar pruning, though bitmask subset enumeration is typically faster.
Recommended for interviews: The bitmasking with subset enumeration approach is the expected solution. It demonstrates understanding of bit representation, subset generation, and hash-based counting. Mentioning the brute force approach first shows baseline reasoning, but implementing the optimized bitmask solution proves you can handle high-constraint problems efficiently.
Approach 1: Bitmask Approach
Utilize bitmasks to represent words and puzzles. This allows for quick inclusion checks (using bitwise AND) and processing of the large dataset efficiently.
We construct a bitmask for each word and store it in a dictionary with counts. For each puzzle, generate all possible submasks (the example uses a different method) and check if they are present in the preprocessed dictionary.
The solution involves the following steps:
- Create a bitmask for each word that indicates which characters are included.
- Store these bitmasks in a dictionary (or hashmap) with their occurrence counts.
- For each puzzle, generate all possible bitmasks that include the first character and check against the stored word bitmasks.
Code
Python
Complexity
Time Complexity: O(W + P * 27), where W is the number of words and P is the number of puzzles.
Space Complexity: O(W), due to storing the bitmask of each word.
Approach 2: Brute Force Approach
Loop through each puzzle and for each puzzle, check every word in the word list to see if it is valid. This approach is straightforward but inefficient for larger datasets.
Check each word against each puzzle, ensuring the word contains the first letter of the puzzle and no characters not in the puzzle. This approach is easy to understand but computationally expensive.
Code
Python
Complexity
Time Complexity: O(W * P * L), where W is the number of words, P is the number of puzzles, and L is the average length of the words.
Space Complexity: O(1), as no additional data structures are used that scale with input size.
Approach 3: Bitmasking with Precomputation
Using a bitmask, we can represent the presence of each letter in a word or puzzle as a single integer. Each bit in this integer corresponds to a letter from 'a' to 'z'.
For each word, compute its bitmask and store it in a hash map with its frequency. When processing puzzles, derive all potential subsets of the puzzle's bitmask that contain the first letter of the puzzle. Use the precomputed hash map to count how many words have matching character sets.
This solution first converts each word into a bitmask representing the presence of its characters using a get_bitmask function. The word_count dictionary stores the number of words for each bitmask.
For each puzzle, it generates the bitmask and processes each subset that includes the first puzzle letter using bit manipulation. It checks each subset against precomputed word masks for potential matches and counts them. This avoids unnecessary recomputation and efficiently selects valid words.
Code
Python
JavaScript
Complexity
Time Complexity: O(N + P * 2^L), where N is the number of words, P is the number of puzzles, and L is the max number of letters in the puzzle (L = 7), resulting in 2^L subsets.
Space Complexity: O(N) for storing bitmasks and their frequencies.
Approach 4: Direct Check with Early Stopping
This approach uses direct validation of each word against each puzzle by checking the conditions separately using set operations. Early stopping is applied if any character not in the puzzle is found or if the word doesn't contain the first puzzle character.
This Java solution leverages set membership tests for characters to ensure each word meets the puzzle's requirements. For each puzzle, it tracks characters in a set and verifies if each word abides by puzzle constraints, including early stopping.
The solution is less efficient for larger input sizes but straightforward to understand and implement directly.
Code
Java
Complexity
Time Complexity: O(P * N * L), where P is the number of puzzles, N is the number of words, and L is the average length of each word.
Space Complexity: O(1) additional space besides input storage.
Approach 5: State Compression + Hash Table + Subset Enumeration
According to the problem description, for each puzzle p in the puzzle array puzzles, we need to count how many words w contain the first letter of the puzzle p, and every letter in w can be found in p.
Since each repeated letter in a word only needs to be counted once, we can use the method of binary state compression to convert each word w into a binary number mask, where the ith bit of mask is 1 if and only if the letter i appears in the word w. We use a hash table cnt to count the number of times each compressed state of all words appears.
Next, we traverse the puzzle array puzzles. For each puzzle p, we note that its length is fixed at 7, so we only need to enumerate the subsets of p. If the subset contains the first letter of p, then we look up its corresponding value in the hash table and add it to the current puzzle's answer.
After the traversal, we can get the number of puzzle solutions corresponding to each puzzle in the puzzle array puzzles, and return it.
The time complexity is O(m times |w| + n times 2^{|p|}), and the space complexity is O(m). Here, m and n are the lengths of the arrays words and puzzles respectively, and |w| and |p| are the maximum length of the words in the array words and the length of the puzzles in the array puzzles, respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Bitmask Approach | Time Complexity: O(W + P * 27), where W is the number of words and P is the number of puzzles. |
| Brute Force Approach | Time Complexity: O(W * P * L), where W is the number of words, P is the number of puzzles, and L is the average length of the words. |
| Bitmasking with Precomputation | Time Complexity: O(N + P * 2^L), where N is the number of words, P is the number of puzzles, and L is the max number of letters in the puzzle (L = 7), resulting in 2^L subsets. Space Complexity: O(N) for storing bitmasks and their frequencies. |
| Direct Check with Early Stopping | Time Complexity: O(P * N * L), where P is the number of puzzles, N is the number of words, and L is the average length of each word. Space Complexity: O(1) additional space besides input storage. |
| State Compression + Hash Table + Subset Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Check | O(W * P * L) | O(1) | Understanding constraints or very small inputs |
| Direct Check with Early Stopping | ~O(W * P) | O(1) | Simple optimized baseline without bit operations |
| Bitmask Approach | O(W * P) | O(W) | When using fast subset checks via bit operations |
| Bitmasking with Precomputation | O(W + P * 2^6) | O(W) | Optimal approach for large inputs and interview settings |
Video Solution
Number of Valid Words for Each Puzzle | Bit Manipulation | Leetcode Hard Solutions • Pepcoding • 16,423 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Valid Words for Each Puzzle easy or hard?
Number of Valid Words for Each Puzzle Python/Java solution
How to solve Number of Valid Words for Each Puzzle in O(n)?
What is the best approach for Number of Valid Words for Each Puzzle?
Is Number of Valid Words for Each Puzzle asked at Google/Amazon/Meta?
What data structure is used in Number of Valid Words for Each Puzzle?
What is the time complexity of Number of Valid Words for Each Puzzle?
Ready to solve this problem?
Practice Number of Valid Words for Each Puzzle with our built-in code editor and test cases.
Practice on FleetCode