Number of Valid Words for Each Puzzle

Number of Valid Words for Each Puzzle

What is this problem about?

The Number of Valid Words for Each Puzzle problem gives you a list of words and a list of puzzles. A word is valid for a puzzle if all characters of the word appear in the puzzle AND the first character of the puzzle appears in the word. Count valid words per puzzle efficiently. This hard coding problem uses bitmask representation for O(1) word-puzzle matching.

Why is this asked in interviews?

Dropbox asks this because the naive O(words × puzzles × word_length) approach is too slow. The efficient solution encodes each word as a bitmask of its characters, groups words by bitmask in a hash map, then for each puzzle enumerates all submasks of the puzzle's bitmask to count matching words. The array, hash table, trie, string, and bit manipulation interview pattern is the core.

Algorithmic pattern used

Bitmask word frequency map + submask enumeration. Encode each word as a 26-bit mask. Build freq[mask] = number of words with exactly that bitmask. For each puzzle: encode puzzle as a 26-bit mask. The first character of the puzzle must appear in the word (fix that bit). Enumerate all submasks of the puzzle mask that include the first-character bit. Sum freq[submask] for all valid submasks.

Example explanation

puzzle="abcde", first_char='a'. Puzzle mask = 11111 (bits for a,b,c,d,e). Words with characters ⊆ puzzle and containing 'a': words whose bitmask is a submask of puzzle_mask that has bit 'a' set. Submask enumeration: start from puzzle_mask, iteratively remove bits using (submask-1) & puzzle_mask until submask=0.

Common mistakes candidates make

• Not requiring the first puzzle character in the word (easy to miss).
• Not grouping words by bitmask (iterating all words per puzzle is too slow).
• Incorrect submask enumeration (must include first_char_bit in all valid submasks).
• O(2^26) submask space — prune by only enumerating 7-character puzzle submasks (at most 2^7=128).

Interview preparation tip

Bitmask submask enumeration is a powerful technique: to enumerate all submasks of a mask m, iterate: sub = m; while sub > 0: process(sub); sub = (sub-1) & m. This visits all 2^popcount(m) submasks. For puzzles of length 7, this is only 128 iterations. Memorize this enumeration pattern — it appears in several hard bitmask problems involving "find all subsets satisfying a constraint."