Problem Description

You are given two arrays: words and puzzles.
For each puzzle in puzzles, you need to find out how many words in words are valid with respect to that puzzle. A word is considered valid for a puzzle if:

• All the letters of the word are contained in the puzzle (the puzzle is a string of 7 unique lowercase letters).
• The word contains the first letter of the puzzle.

• Each puzzle contains 7 unique letters.
• Words and puzzles may be up to 10⁵ in size.
• All words are lowercase and may be up to 50 letters long.
• Efficiency is crucial due to the input size.

Thought Process

At first glance, the problem suggests checking every word against every puzzle, but this would be too slow for large inputs. To be valid, a word must:

• Have all its letters present in the puzzle (i.e., be a subset of the puzzle's letters).
• Contain the puzzle's first letter.

Solution Approach

The solution relies on bit manipulation and hash maps for efficiency. Here’s a step-by-step breakdown:

1. Represent words and puzzles as bitmasks:
   • Each word and puzzle can be represented as a 26-bit integer, where each bit corresponds to a letter ('a' = 0, 'b' = 1, ...).
   • For example, the word "abc" would have bits 0, 1, and 2 set.
2. Count word bitmask frequencies:
   • For each word, compute its bitmask and count how many times each unique bitmask occurs. This allows for fast lookups later.
3. For each puzzle, enumerate all subsets that include the first letter:
   • Since each puzzle has 7 unique letters, there are 2⁷ = 128 possible subsets.
   • For each subset, if it contains the first letter of the puzzle, check if any word uses exactly that subset of letters (using the frequency map).
   • Sum the counts for all valid subsets.
4. Collect results:
   • For each puzzle, the total count is the answer for that puzzle.

Example Walkthrough

Sample Input:
words = ["apple", "pleas", "please"]
puzzles = ["aelwxyz", "aelpxyz", "aelpsxy", "saelpxy"]

Step-by-Step:

• Convert words to bitmasks:
  • "apple" → {'a','p','l','e'} → bitmask 000...0001011001
  • "pleas" → {'p','l','e','a','s'} → bitmask 000...0101011001
  • "please" → {'p','l','e','a','s'} (same as "pleas")
• Count frequencies:
  • bitmask for "apple": 1
  • bitmask for "pleas"/"please": 2
• For each puzzle, enumerate subsets including first letter:
  • For "aelwxyz", first letter = 'a'
  • Enumerate all subsets of "aelwxyz" that include 'a'
  • Check if any word bitmask matches these subsets
• Sum frequencies:
  • Count how many times each subset appears in word frequencies
  • Return the sum for each puzzle

• For "aelwxyz": only "apple" is valid → 1
• For "aelpxyz": "apple" and "pleas" are valid → 2
• For "aelpsxy": "pleas" and "please" are valid → 2
• For "saelpxy": "pleas" and "please" are valid → 2

Time and Space Complexity

Brute-force approach:

• Time: O(N * M * L), where N = number of words, M = number of puzzles, L = average word length.
• This is infeasible for large inputs (up to 10¹⁰ operations).

• Time: O(N + M * 2^7), where N = words, M = puzzles, 2^7 = 128 (subsets per puzzle).
• Space: O(N), for storing the word bitmask frequencies.
• This is efficient and works within the problem's constraints.

• Each word is processed once to build the frequency map.
• For each puzzle, we check up to 128 subsets, which is fast.

Summary

The key to solving this problem efficiently is to leverage the small size of each puzzle (7 unique letters) and use bitmasking to represent sets of letters. By pre-processing the words into a frequency map of bitmasks, we can quickly count valid words for each puzzle by enumerating all possible subsets of the puzzle's letters that include the first letter. This approach is elegant because it transforms a seemingly intractable problem into one that is both efficient and easy to understand using bit manipulation and hash maps.

Code Implementation

from typing import List
from collections import Counter

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        def word_to_bitmask(word):
            mask = 0
            for ch in set(word):
                mask |= 1 << (ord(ch) - ord('a'))
            return mask

        word_count = Counter()
        for word in words:
            mask = word_to_bitmask(word)
            # Only consider words with up to 7 unique letters
            if bin(mask).count('1') <= 7:
                word_count[mask] += 1

        res = []
        for puzzle in puzzles:
            total = 0
            first = 1 << (ord(puzzle[0]) - ord('a'))
            # Generate all subsets of puzzle
            mask = 0
            for ch in puzzle:
                mask |= 1 << (ord(ch) - ord('a'))
            sub = mask
            while sub:
                if sub & first:
                    total += word_count.get(sub, 0)
                sub = (sub - 1) & mask
            res.append(total)
        return res
      

#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        unordered_map<int, int> word_count;
        for (const string& word : words) {
            int mask = 0;
            for (char ch : word)
                mask |= 1 << (ch - 'a');
            if (__builtin_popcount(mask) <= 7)
                ++word_count[mask];
        }
        vector<int> res;
        for (const string& puzzle : puzzles) {
            int mask = 0;
            for (char ch : puzzle)
                mask |= 1 << (ch - 'a');
            int first = 1 << (puzzle[0] - 'a');
            int total = 0;
            int sub = mask;
            do {
                if (sub & first)
                    total += word_count[sub];
                sub = (sub - 1) & mask;
            } while (sub != mask);
            res.push_back(total);
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        Map<Integer, Integer> wordCount = new HashMap<>();
        for (String word : words) {
            int mask = 0;
            for (char ch : word.toCharArray())
                mask |= 1 << (ch - 'a');
            if (Integer.bitCount(mask) <= 7)
                wordCount.put(mask, wordCount.getOrDefault(mask, 0) + 1);
        }
        List<Integer> res = new ArrayList<>();
        for (String puzzle : puzzles) {
            int mask = 0;
            for (char ch : puzzle.toCharArray())
                mask |= 1 << (ch - 'a');
            int first = 1 << (puzzle.charAt(0) - 'a');
            int total = 0;
            int sub = mask;
            while (true) {
                if ((sub & first) != 0)
                    total += wordCount.getOrDefault(sub, 0);
                if (sub == 0) break;
                sub = (sub - 1) & mask;
            }
            res.add(total);
        }
        return res;
    }
}
      

/**
 * @param {string[]} words
 * @param {string[]} puzzles
 * @return {number[]}
 */
var findNumOfValidWords = function(words, puzzles) {
    const wordCount = new Map();
    for (const word of words) {
        let mask = 0;
        for (const ch of new Set(word))
            mask |= 1 << (ch.charCodeAt(0) - 97);
        if (mask.toString(2).split('1').length - 1 <= 7)
            wordCount.set(mask, (wordCount.get(mask) || 0) + 1);
    }
    const res = [];
    for (const puzzle of puzzles) {
        let mask = 0;
        for (const ch of puzzle)
            mask |= 1 << (ch.charCodeAt(0) - 97);
        const first = 1 << (puzzle.charCodeAt(0) - 97);
        let total = 0;
        let sub = mask;
        while (sub) {
            if (sub & first)
                total += wordCount.get(sub) || 0;
            sub = (sub - 1) & mask;
        }
        res.push(total);
    }
    return res;
};