Number of Valid Words for Each Puzzle

hard bitmask submask enumeration hash map

Problem

Given an array of words and an array of puzzles, a word is valid for a puzzle if (1) the word contains the puzzle's first letter and (2) every letter of the word appears somewhere in the puzzle. Return, for each puzzle, the number of valid words. Each puzzle has exactly 7 distinct letters.

Inputwords = ["aaaa","asas","able","ant","cat"], puzzles = ["aboveyz"]

Output[1]

Puzzle "aboveyz" has first letter 'a' and letter set {a,b,e,o,v,y,z}. A valid word must contain 'a' and use only those letters: "aaaa" ✓; "asas" has 's' ✗; "able" has 'l' ✗; "ant" has 'n','t' ✗; "cat" has 'c','t' ✗. So exactly 1 word is valid.

words (comma-separated)

puzzle (7 distinct letters)

def find_num_of_valid_words(words, puzzles):
    cnt = {}
    for w in words:
        mask = 0
        for ch in w:
            mask |= 1 << (ord(ch) - 97)
        cnt[mask] = cnt.get(mask, 0) + 1
    res = []
    for p in puzzles:
        pmask = 0
        for ch in p:
            pmask |= 1 << (ord(ch) - 97)
        first = 1 << (ord(p[0]) - 97)
        total, sub = 0, pmask
        while sub:
            if sub & first:
                total += cnt.get(sub, 0)
            sub = (sub - 1) & pmask
        res.append(total)
    return res

function findNumOfValidWords(words, puzzles) {
  const cnt = new Map();
  for (const w of words) {
    let mask = 0;
    for (const ch of w) mask |= 1 << (ch.charCodeAt(0) - 97);
    cnt.set(mask, (cnt.get(mask) || 0) + 1);
  }
  const res = [];
  for (const p of puzzles) {
    let pmask = 0;
    for (const ch of p) pmask |= 1 << (ch.charCodeAt(0) - 97);
    const first = 1 << (p.charCodeAt(0) - 97);
    let total = 0, sub = pmask;
    while (sub) {
      if (sub & first) total += cnt.get(sub) || 0;
      sub = (sub - 1) & pmask;
    }
    res.push(total);
  }
  return res;
}

class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (String w : words) {
            int mask = 0;
            for (char ch : w.toCharArray()) mask |= 1 << (ch - 'a');
            cnt.merge(mask, 1, Integer::sum);
        }
        List<Integer> res = new ArrayList<>();
        for (String p : puzzles) {
            int pmask = 0;
            for (char ch : p.toCharArray()) pmask |= 1 << (ch - 'a');
            int first = 1 << (p.charAt(0) - 'a');
            int total = 0, sub = pmask;
            while (sub != 0) {
                if ((sub & first) != 0) total += cnt.getOrDefault(sub, 0);
                sub = (sub - 1) & pmask;
            }
            res.add(total);
        }
        return res;
    }
}

vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
    unordered_map<int, int> cnt;
    for (auto& w : words) {
        int mask = 0;
        for (char ch : w) mask |= 1 << (ch - 'a');
        cnt[mask]++;
    }
    vector<int> res;
    for (auto& p : puzzles) {
        int pmask = 0;
        for (char ch : p) pmask |= 1 << (ch - 'a');
        int first = 1 << (p[0] - 'a');
        int total = 0, sub = pmask;
        while (sub) {
            if (sub & first) total += cnt.count(sub) ? cnt[sub] : 0;
            sub = (sub - 1) & pmask;
        }
        res.push_back(total);
    }
    return res;
}

Explanation

A word is valid for a puzzle when it uses only the puzzle's letters and contains the puzzle's first letter. Checking every word against every puzzle directly would be far too slow, so we encode letters as bits and reuse work.

First we turn each word into a 26-bit mask where bit i is set if letter i appears. Two words that use the same set of distinct letters get the same mask, so we store counts in a map cnt[mask]. The actual order or repetition of letters does not matter for validity.

For each puzzle we build its mask pmask and the single-bit mask first for its first letter. A word is valid exactly when its mask is a submask of pmask (all its letters fit inside the puzzle) and it includes first.

We enumerate every submask of pmask with the loop sub = (sub - 1) & pmask. For each submask that contains first, we add cnt[sub] to the total. Since a puzzle has only 7 letters, there are at most 2^7 = 128 submasks to check.

Example: puzzle "aboveyz" has first letter a. The word "aaaa" maps to just {a}, which is a submask containing a, so it counts — giving the answer 1.

Time: O(Σ|word| + n·2⁷) Space: O(m)