Number of Valid Words for Each Puzzle - Video Solutions

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.