Number of Valid Words for Each Puzzle — Bitmask Subset Enumeration with Bitwise AND OR

Problem Statement#

You are given a list of words and a list of puzzles. A word is valid for a puzzle if:

1. The word contains the first letter of the puzzle, AND
2. Every letter of the word appears in the puzzle.

Return an array result where result[i] is the number of valid words for puzzles[i].

Constraints:

• 1 <= words.length <= 10^5
• 1 <= puzzles.length <= 10^4
• 4 <= words[i].length <= 50
• puzzles[i].length == 7
• words[i] and puzzles[i] use only lowercase English letters.
• All puzzles[i] are distinct and have unique letters.

Examples:

Input:
  words   = ["aaaa","asas","able","ability","actt","actor","access"]
  puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1, 1, 3, 2, 4, 0]
 
Input:
  words   = ["apple","pleas","please"]
  puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0, 1, 3, 2, 0]

Why This Problem Matters#

Naive brute force is O(W * P * L) — for every word check every puzzle. With W = 10^5 and P = 10^4, that's a trillion comparisons. The fix is one of the most beautiful bit manipulation patterns in interviewing: encode each word as a 26-bit letter set, count occurrences, then for each puzzle enumerate the 64 subsets of its 7-letter alphabet that include the first letter. Total work: O(W * L + P * 64). This trick — Gosper's submask enumeration via sub = (sub - 1) & parent — appears in Google, Amazon, and Meta hard-tier interviews and is a hallmark of strong bit fluency.

The Core Insight (the bit-trick)#

Two layered insights:

1) Word fingerprint = 26-bit OR mask. Two words with the same set of distinct letters are interchangeable for this problem. Reduce each word to a single 26-bit integer (mask |= 1 << (c - 'a')) and store frequencies in a hashmap keyed on that mask. Words with more than 7 distinct letters can never be valid for any 7-letter puzzle, so drop them at ingest.

2) Submask enumeration. A puzzle has exactly 7 letters, giving 128 possible subsets. We need only those subsets that contain the first letter — half of them, so 64. The textbook trick to enumerate every submask of a mask pmask is:

sub = pmask
while sub > 0:
    process(sub)
    sub = (sub - 1) & pmask

This walks every subset of pmask in descending order in O(2^k) time where k is the popcount. To filter for "contains first letter," check sub & first before counting.

The & first filter is what enforces puzzle rule #1; reading from the precomputed word_counts[sub] enforces rule #2 implicitly because we built those keys from words whose entire letter set fit in a puzzle.

Visual Dry Run (binary representation trace)#

Take words = ["apple", "pleas"], puzzle = "aelpxyz".

Word fingerprints (26-bit masks, only relevant bits shown):
  "apple" -> {a,p,l,e}  -> binary set bits at a,e,l,p
  "pleas" -> {p,l,e,a,s} -> bits at a,e,l,p,s
 
word_counts = { {a,e,l,p}: 1, {a,e,l,p,s}: 1 }
 
Puzzle "aelpxyz":
  pmask = bits at {a,e,l,p,x,y,z}, popcount = 7
  first = bit at a
 
Enumerate submasks containing 'a':
  sub = pmask                       -> contains a? yes; lookup -> miss (no word covers x,y,z)
  sub = (pmask - 1) & pmask         -> drop one bit; check ...
  ... (64 of the 128 subsets pass the 'first' filter)
  
  When sub == {a,e,l,p}            -> word_counts hit, +1
  When sub == {a,e,l,p,s}          -> NOT a submask of pmask (s is not in puzzle), so this submask is never visited
  
  Total = 1

The genius is that word_counts[{a,e,l,p,s}] is never queried during this puzzle's enumeration because s is not a bit of pmask. The submask enumeration intrinsically respects the puzzle's letter constraint.

Solution (Optimal)#

Python#

from collections import Counter
 
class Solution:
    def findNumOfValidWords(self, words: list[str], puzzles: list[str]) -> list[int]:
        word_counts = Counter()
        for w in words:
            mask = 0
            for c in w:
                mask |= 1 << (ord(c) - ord('a'))
            if bin(mask).count('1') <= 7:
                word_counts[mask] += 1
 
        result = []
        for p in puzzles:
            pmask = 0
            for c in p:
                pmask |= 1 << (ord(c) - ord('a'))
            first = 1 << (ord(p[0]) - ord('a'))
 
            count = 0
            sub = pmask
            while sub > 0:
                if sub & first:
                    count += word_counts.get(sub, 0)
                sub = (sub - 1) & pmask
 
            result.append(count)
        return result

JavaScript#

var findNumOfValidWords = function (words, puzzles) {
  const wordCounts = new Map();
  for (const w of words) {
    let mask = 0;
    for (const c of w) mask |= 1 << (c.charCodeAt(0) - 97);
    let bits = mask, popcount = 0;
    while (bits) { bits &= bits - 1; popcount++; }
    if (popcount <= 7) wordCounts.set(mask, (wordCounts.get(mask) || 0) + 1);
  }
 
  const result = [];
  for (const p of puzzles) {
    let pmask = 0;
    for (const c of p) pmask |= 1 << (c.charCodeAt(0) - 97);
    const first = 1 << (p.charCodeAt(0) - 97);
 
    let count = 0, sub = pmask;
    while (sub > 0) {
      if (sub & first) count += wordCounts.get(sub) || 0;
      sub = (sub - 1) & pmask;
    }
    result.push(count);
  }
  return result;
};

Complexity: Time O(W * L + P * 2^7) = O(W * L + P * 128). Space O(W) for the counter.

Common Mistakes#

• Forgetting the popcount <= 7 filter. Words with more than 7 distinct letters are never valid; storing them inflates the map.
• Using sub > 0 vs sub >= 0. With >= 0 the loop never terminates because (0 - 1) & pmask = pmask. Use strict > 0 and skip the empty submask (which can't satisfy first anyway).
• Iterating over all 26-bit subsets per puzzle. That's 2^26 per puzzle and times out. The submask trick keeps you bounded by 2^7 = 128.
• Storing puzzle masks in the counter. Counter keys are word masks; puzzles are queries.
• Reapplying the first-letter filter on words. Don't — the puzzle's first letter varies, so words must be stored regardless of which letters they contain.

Interview Tips#

• Open by computing the brute-force complexity (10^9) to motivate the optimization. Then say "I'll fingerprint each word as a 26-bit mask."
• Explain Gosper's submask enumeration (sub = (sub - 1) & pmask) — most candidates haven't seen it. Drawing the recurrence on the whiteboard wins points.
• Justify the popcount <= 7 filter: any word with 8+ distinct letters can't fit inside a 7-letter puzzle.
• Mention the alternative Trie of sorted unique letters approach as a backup. It's slower but more intuitive and a good fallback if you forget the bit trick mid-interview.

Follow-up Questions#

1. Puzzles with variable length k. Submask enumeration is O(2^k); for k > 20 it stops being practical and you switch to inclusion-exclusion or trie-based pruning.
2. Stream of puzzles arriving online. Precompute word_counts once; each query is O(2^k) independent.
3. Stream of words. Maintain word_counts incrementally; queries unaffected.
4. Top-K most-matched words per puzzle. Store the actual words (not just counts) per mask, deduplicate at query time.
5. Allow letter repetitions in the word. Doesn't change the bitmask (sets are repetition-free) — exactly the same algorithm.

Key Takeaways#

• Encoding letter sets as 26-bit OR masks turns string comparison into integer comparison.
• Gosper's submask enumeration sub = (sub - 1) & parent walks all subsets in O(2^k).
• Filter words with popcount > 7 early — they can't possibly fit a 7-letter puzzle.
• The sub & first check enforces "must contain first puzzle letter" in a single bitwise AND.
• Total complexity drops from O(W * P * L) to O(W * L + P * 128) — a 6+ order of magnitude speedup.
• This pattern recurs in subset-sum DP, Steiner tree DP, and many combinatorial enumeration problems.