# Number of Valid Words for Each Puzzle
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-valid-words-for-each-puzzle)
Canonical: https://scaleengineer.com/dsa/problems/number-of-valid-words-for-each-puzzle
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table, String, Trie
**Companies:** [Dropbox](https://scaleengineer.com/companies/dropbox)
---
## Problem
With respect to a given `puzzle` string, a `word` is _valid_ if both the following conditions are satisfied: 
* `word` contains the first letter of `puzzle`.
* For each letter in `word`, that letter is in `puzzle`.  
  * For example, if the puzzle is `"abcdefg"`, then valid words are `"faced"`, `"cabbage"`, and `"baggage"`, while
  * invalid words are `"beefed"` (does not include `'a'`) and `"based"` (includes `'s'` which is not in the puzzle).
Return _an array_ `answer`_, where_ `answer[i]` _is the number of words in the given word list_ `words` _that is valid with respect to the puzzle_ `puzzles[i]`. 

**Example 1:**

**Input:** words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
**Output:** [1,1,3,2,4,0]
**Explanation:** 
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There are no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

**Example 2:**

**Input:** words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
**Output:** [0,1,3,2,0]

**Constraints:**

* `1 <= words.length <= 105`
* `4 <= words[i].length <= 50`
* `1 <= puzzles.length <= 104`
* `puzzles[i].length == 7`
* `words[i]` and `puzzles[i]` consist of lowercase English letters.
* Each `puzzles[i] `does not contain repeated characters.

# Approaches
## Brute Force with Character Set
This approach directly translates the problem statement into code. It iterates through each puzzle and, for each puzzle, it checks every single word from the list to see if it meets the two validity conditions. While straightforward, its performance is poor due to the nested loops over puzzles and words.
**Time:** O(M * N * L), where M is the number of puzzles, N is the number of words, and L is the maximum length of a word. With the given constraints (M=10^4, N=10^5, L=50), this is approximately 10^4 * 10^5 * 50, which is far too slow. · **Space:** O(P), where P is the length of a puzzle. Since P is fixed at 7, the space complexity is effectively O(1). This space is used for the `HashSet` of puzzle characters.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** Extremely inefficient for the given constraints.; Results in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The algorithm's core is a nested loop structure. The outer loop processes one puzzle at a time. For each puzzle, the inner loop iterates through the entire list of words. To verify if a word is valid, we perform two checks:
1.  **First Letter Condition:** The word must contain the first letter of the puzzle.
2.  **Character Set Condition:** All characters in the word must be present in the puzzle.

To make the second check faster than repeated string searches, we can first convert the puzzle string into a `HashSet` of its characters. This allows checking for a character's existence in `O(1)` average time. Despite this optimization, the overall complexity remains high because we still have to examine every word for every puzzle.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        List<Integer> result = new ArrayList<>();
        for (String puzzle : puzzles) {
            int count = 0;
            char firstChar = puzzle.charAt(0);
            Set<Character> puzzleChars = new HashSet<>();
            for (char c : puzzle.toCharArray()) {
                puzzleChars.add(c);
            }

            for (String word : words) {
                boolean isValid = true;
                boolean hasFirstChar = false;
                for (char c : word.toCharArray()) {
                    if (c == firstChar) {
                        hasFirstChar = true;
                    }
                    if (!puzzleChars.contains(c)) {
                        isValid = false;
                        break;
                    }
                }
                if (isValid && hasFirstChar) {
                    count++;
                }
            }
            result.add(count);
        }
        return result;
    }
}
```
### Algorithm
*   Initialize an empty list `answer` to store the results.
*   Iterate through each `puzzle` in the `puzzles` array.
    *   Initialize a counter `count` for valid words to 0.
    *   Extract the first character of the puzzle, `firstChar`.
    *   Create a `HashSet` of characters from the `puzzle` string for efficient lookups (`puzzleChars`).
    *   Iterate through each `word` in the `words` array.
        *   Assume the word is valid by setting a flag `isValid` to `true`.
        *   Keep track if the `firstChar` is found in the word with a flag `hasFirstChar`.
        *   Iterate through each character `c` of the `word`.
            *   If `c` matches `firstChar`, set `hasFirstChar` to `true`.
            *   If `c` is not present in `puzzleChars`, the word is invalid. Set `isValid` to `false` and break the inner loop.
        *   After checking all characters, if `isValid` and `hasFirstChar` are both `true`, increment the `count`.
    *   Add the final `count` for the current puzzle to the `answer` list.
*   Return the `answer` list.

## Bitmasking with Submask Iteration
This highly efficient approach uses bitmasks to represent sets of characters. The key insight is to reframe the problem from 'for each puzzle, check all words' to 'for each puzzle, find all valid word types'. Since puzzles have a fixed small length (7), the number of possible character subsets is also small (2^7 = 128).
**Time:** O(N*L + M*2^P), where N is `words.length`, L is max `word.length`, M is `puzzles.length`, and P is `puzzle.length` (7).
- `O(N*L)` to build the frequency map from the words.
- `O(M*2^P)` to process the puzzles by iterating through submasks.
This is well within the time limits. · **Space:** O(U), where U is the number of unique character bitmasks among the words. In the worst case, U can be equal to N (the number of words), so the complexity is O(N).
**Pros:** Highly efficient and passes the time limits for the given constraints.; Effectively utilizes the problem's constraints (small alphabet, fixed puzzle length).; Decouples the dependency between the number of words and puzzles, leading to an additive complexity rather than multiplicative.
**Cons:** More complex to understand, requiring knowledge of bit manipulation.; The submask iteration technique is not immediately obvious.
### Explanation
We can represent the character set of any word or puzzle using a 26-bit integer, where each bit corresponds to a letter of the alphabet. This is called a bitmask.

**Step 1: Preprocessing Words**
First, we process the `words` list. For each word, we calculate its unique character bitmask. We then store the frequency of each bitmask in a `HashMap`. This is efficient because many words might share the same character set (e.g., "apple" and "appeal").

**Step 2: Processing Puzzles**
Next, we iterate through each `puzzle`. For a given puzzle, a word is valid if its character set is a subset of the puzzle's character set, and it contains the puzzle's first letter. In terms of bitmasks, this means:
1.  `wordMask` is a submask of `puzzleMask` (i.e., `(wordMask & puzzleMask) == wordMask`).
2.  `wordMask` has the bit for the puzzle's first character set.

Instead of checking our entire map of word masks, we can generate all possible valid masks directly from the `puzzleMask`. We do this by iterating through all submasks of the `puzzleMask`. Since a puzzle has only 7 characters, there are at most `2^7 = 128` submasks to check for each puzzle, which is a small, constant number. For each submask that satisfies the first-letter condition, we add its frequency from our precomputed map to the puzzle's total count.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        Map<Integer, Integer> wordMaskFreq = new HashMap<>();
        for (String word : words) {
            int mask = 0;
            for (char c : word.toCharArray()) {
                mask |= (1 << (c - 'a'));
            }
            // Optimization: A word with more than 7 unique characters can never be valid.
            if (Integer.bitCount(mask) <= 7) {
                wordMaskFreq.put(mask, wordMaskFreq.getOrDefault(mask, 0) + 1);
            }
        }

        List<Integer> result = new ArrayList<>();
        for (String puzzle : puzzles) {
            int count = 0;
            int puzzleMask = 0;
            for (char c : puzzle.toCharArray()) {
                puzzleMask |= (1 << (c - 'a'));
            }
            
            int firstCharMask = 1 << (puzzle.charAt(0) - 'a');
            
            // Iterate through all submasks of the puzzle's mask
            int submask = puzzleMask;
            while (submask > 0) {
                // Check if the submask contains the first character of the puzzle
                if ((submask & firstCharMask) == firstCharMask) {
                    count += wordMaskFreq.getOrDefault(submask, 0);
                }
                // Move to the next submask
                submask = (submask - 1) & puzzleMask;
            }
            result.add(count);
        }
        return result;
    }
}
```
### Algorithm
*   Initialize a `HashMap<Integer, Integer>` called `wordMaskFreq` to store the frequency of each word's character bitmask.
*   **Preprocessing Words:**
    *   Iterate through each `word` in the `words` array.
    *   For each word, compute its bitmask. A bitmask is an integer where the i-th bit is 1 if the character `'a' + i` is in the word.
    *   Optionally, filter out words with more than 7 unique characters, as they can never be valid for a 7-letter puzzle.
    *   Store the computed mask in the `wordMaskFreq` map, incrementing its frequency count.
*   **Processing Puzzles:**
    *   Initialize an empty list `answer`.
    *   Iterate through each `puzzle` in the `puzzles` array.
    *   Initialize a `count` for the current puzzle to 0.
    *   Compute the `puzzleMask` for the current puzzle.
    *   Get the bitmask for the puzzle's first character, `firstCharMask`.
    *   Iterate through all submasks of the `puzzleMask`. A clever way to do this is with the loop `for (int submask = puzzleMask; submask > 0; submask = (submask - 1) & puzzleMask)`.
    *   For each `submask`:
        *   Check if it contains the first character's bit: `(submask & firstCharMask) != 0`.
        *   If it does, this `submask` represents a potential valid word's character set. Look up its frequency in `wordMaskFreq` and add it to `count`.
    *   Add the total `count` to the `answer` list.
*   Return the `answer` list.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
    Map<Integer, Integer> cnt = new HashMap<>(words.length);
    for (var w : words) {
      int mask = 0;
      for (int i = 0; i < w.length(); ++i) {
        mask |= 1 << (w.charAt(i) - 'a');
      }
      cnt.merge(mask, 1, Integer : : sum);
    }
    List<Integer> ans = new ArrayList<>();
    for (var p : puzzles) {
      int mask = 0;
      for (int i = 0; i < p.length(); ++i) {
        mask |= 1 << (p.charAt(i) - 'a');
      }
      int x = 0;
      int i = p.charAt(0) - 'a';
      for (int j = mask; j > 0; j = (j - 1) & mask) {
        if ((j >> i & 1) == 1) {
          x += cnt.getOrDefault(j, 0);
        }
      }
      ans.add(x);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findNumOfValidWords(vector<string> &words,
                                  vector<string> &puzzles) {
    unordered_map<int, int> cnt;
    for (auto &w : words) {
      int mask = 0;
      for (char &c : w) {
        mask |= 1 << (c - 'a');
      }
      cnt[mask]++;
    }
    vector<int> ans;
    for (auto &p : puzzles) {
      int mask = 0;
      for (char &c : p) {
        mask |= 1 << (c - 'a');
      }
      int x = 0;
      int i = p[0] - 'a';
      for (int j = mask; j; j = (j - 1) & mask) {
        if (j >> i & 1) {
          x += cnt[j];
        }
      }
      ans.push_back(x);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]: cnt = Counter() for w in words: mask = 0 for c in w: mask |= 1 << (ord(c) - ord("a")) cnt[mask] += 1 ans = [] for p in puzzles: mask = 0 for c in p: mask |= 1 << (ord(c) - ord("a")) x, i, j = 0, ord(p[0]) - ord("a"), mask while j: if j >> i & 1: x += cnt[j] j = (j - 1) & mask ans . append(x) return ans

```