Number of Valid Words for Each Puzzle: Bitmask Subset Enumeration

LeetCode Number of Valid Words for Each Puzzle (Problem 1178) asks: given a list of words and a list of puzzles, for each puzzle find how many words are "valid." A word is valid for a puzzle if two conditions hold:

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

Each puzzle is exactly 7 characters long with all distinct letters. Words can be any length and may contain repeated characters. The challenge is doing this efficiently when both lists are large.

Why brute force fails

The naive approach checks every word against every puzzle. For each pair you would verify both conditions. With up to 100,000 words and 10,000 puzzles, that is a billion checks. Even with early exits, this is too slow.

The key to making it fast is recognizing that what matters about a word is not its length or letter frequencies, but only which unique letters it contains. Two words like "aabd" and "dba" are equivalent for validity purposes. This is where bitmasks come in.

The bitmask representation

Since both words and puzzles use only lowercase English letters, you can represent the set of unique letters in any string as a 26-bit integer. Set bit i if the letter 'a' + i appears in the string. For example, "aabd" becomes 0b1011 (bits for a, b, and d).

With this representation, the two validity conditions become bit operations:

• "Every letter in word appears in puzzle" becomes word_mask & puzzle_mask == word_mask, or equivalently, word_mask is a subset of puzzle_mask.
• "Word contains the first letter of puzzle" becomes word_mask & (1 << first_letter_bit) != 0.

The subset enumeration trick

Here is where the problem gets interesting. A puzzle has 7 distinct letters, so its bitmask has exactly 7 bits set. A word mask that is valid must be a subset of the puzzle mask. There are at most 2^7 = 128 subsets of a 7-bit mask.

Instead of checking every word against the puzzle, you can flip the approach:

1. Precompute a frequency map from word bitmask to count.
2. For each puzzle, enumerate all subsets of its bitmask that include the first letter.
3. For each subset, look it up in the frequency map and add the count.

Enumerating subsets uses the classic bit trick: starting from the full mask, repeatedly compute sub = (sub - 1) & mask until sub reaches 0. This visits every subset exactly once.

Python solution

def find_num_of_valid_words(words, puzzles):
    from collections import Counter

    freq = Counter()
    for w in words:
        mask = 0
        for ch in w:
            mask |= 1 << (ord(ch) - ord('a'))
        if bin(mask).count('1') <= 7:
            freq[mask] += 1

    result = []
    for p in puzzles:
        puzzle_mask = 0
        for ch in p:
            puzzle_mask |= 1 << (ord(ch) - ord('a'))
        first_bit = 1 << (ord(p[0]) - ord('a'))

        count = 0
        sub = puzzle_mask
        while sub:
            if sub & first_bit:
                count += freq[sub]
            sub = (sub - 1) & puzzle_mask
        result.append(count)

    return result

Step-by-step walkthrough

Let's trace through with words = ["aabd", "abcd", "abed"] and puzzles = ["abcdefg"].

The algorithm enumerates 127 subsets of the puzzle mask (all nonempty subsets of 7 bits). Only the subsets that actually appear in the frequency map contribute to the count. Since hash map lookups are O(1), each puzzle takes O(128) time regardless of how many words exist.

Complexity analysis

Building the frequency map takes O(W * L) to compute each word's bitmask. For each puzzle, you enumerate at most 128 subsets and do a hash map lookup for each. The subset enumeration per puzzle is O(128), which is effectively constant. This makes the overall time linear in the input size.

Building blocks

This problem combines three reusable building blocks that CodeBricks drills independently:

Bitmask set representation

Encoding a set of characters as a single integer. Each bit represents whether a character is present. This turns set operations (intersection, subset check, union) into single bitwise operations. You use this pattern whenever you need to compare sets of bounded-size elements efficiently.

Subset enumeration via (sub - 1) & mask

The classic technique for iterating over all subsets of a bitmask. Subtracting 1 flips the lowest set bit and sets all lower bits. AND-ing with the original mask keeps only positions that belong to the original set. This produces every subset in decreasing order and runs in O(2^k) time where k is the number of set bits.

sub = mask
while sub:
    process(sub)
    sub = (sub - 1) & mask

Frequency counting with a hash map

Grouping equivalent items by a computed key and counting them. Here the key is the word bitmask. This collapses potentially millions of words into a small map that you can query in O(1) per lookup.

Edge cases

Words with more than 7 unique letters. These can never match any puzzle, since every puzzle has exactly 7 distinct letters. Filtering them out during preprocessing saves space in the frequency map and avoids pointless lookups.

All words match a puzzle. When every word's unique letters form a subset of the puzzle and all contain its first letter, the answer for that puzzle equals the total number of words. The algorithm handles this naturally through the frequency map.

No words match a puzzle. If no word mask appears among the puzzle's subsets, all lookups return 0 and the result for that puzzle is 0.

Repeated characters in words. Words like "aaaa" produce a mask with a single bit set. The bitmask representation handles this automatically since OR-ing a bit that is already set is a no-op.

From understanding to recall

The two key ideas here, bitmask set representation and subset enumeration, appear in many bit manipulation problems. Understanding them once is not enough. You need to recall the (sub - 1) & mask trick instantly when you see a problem that asks you to iterate over subsets.

Spaced repetition builds that muscle memory. You write the subset enumeration loop from scratch today, then again in a few days, then a week later. Each time, the pattern becomes faster to type and easier to recognize. When you encounter a problem where elements map to a bounded set and you need to check all subsets, the technique will surface immediately.

Related posts

• XOR Cancellation Pattern - Another bit manipulation technique where XOR-ing pairs cancels them out. Complements the bitmask subset approach here by showing a different way bitwise operations simplify set-like reasoning.
• Number of 1 Bits - Counting set bits using n & (n - 1). Builds the foundational bit manipulation skill you need before tackling subset enumeration and bitmask set representations.
• Subsets - Generating all subsets via backtracking. While that problem uses recursion, this problem uses the iterative bitmask approach to achieve the same goal. Seeing both techniques side by side strengthens your toolkit.