
### Problem Statement

###### 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].

**INPUT**

- **words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]**

**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.

**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'.

**Steps To Solve**

- Think of solution without code

  - Given constraints are word must contain 1st letter of puzzle and puzzle must contain all letter of words.
  - Lets take puzzle **abslute** and check
    |aaaa | asas|able |ability |actt |actor|acess|
    | --- | --- | --- | --- | --- |---|---|
    ✅ | ✅ | ✅ | ❌ | ❌ |❌ |❌ |
  - We see that here we need to do a lot of comparisons between characters of word and puzzle.A possible solution to this is using bit masking.
    ![Number of Valid Worlds](https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcQ4_8xg8FIvBRO5QYveeo3PjArAzWC_Wa_-hg&usqp=CAU)
  - We can convert our words into number by setting the bit on and off .For example we can represent **dfac** as **00000000000000000000000000101101 = 45**
  - Lets now see taking an example of word and puzzle
    | | |a|b |c |d |e|f|g|h|i|j|
    | --- | --- | --- | --- | --- |---|---|---|---|---|---|---|
    **puzzle** | **hdbje** | 0 | 1 | 0 |1 |1 |0|0|1|0|1|
    **word** | **bdhge** | 0 | 1 | 0 |1 |1 |0|1|1|0|0|
    **&** | | 0 | 1 | 0 |1 |1 |0|0|1|0|0|
  - If the puzzle contains all the letters of word then
    **word & puzzle = word**.In the above example we saw that it failed as letter g was not present in our puzzle.
  - Now to further optimize our search we can keep a hash map of words containing a particular character, in this way we don't have to search through the entire set of word.
  - Example we will store bitmask of words containing that character.
    | | | | | ||||
    | --- | --- | --- | --- | --- |---|---|---|
    a | aaaa | asas | able | ability |actt |actor |access|
    b | able | ability |
    c |actt |actor |access|
  - Now when we iterate through our puzzle we will only check only those words whose key in hash map, is the first character of our puzzle. So for puzzle **abslute** we will check only those words in hash map with key **a**.

```js
var findNumOfValidWords = function (words, puzzles) {
  let map = new Map();
  let res = [];
  for (let i = 0; i < 26; i++) {
    map.set(String.fromCharCode(i + 97), []);
  }

  for (let word of words) {
    let mask = 0;

    for (let ch of word) {
      let bit = ch.charCodeAt(0) - "a".charCodeAt(0);
      mask |= 1 << bit; // ON the bit of character and OR to combine with rest.
    }

    // we dont want to add same word multiple times for a key
    let unique = new Set();
    for (let ch of word) {
      if (unique.has(ch)) continue;

      unique.add(ch);
      map.get(ch).push(mask);
    }
  }

  for (let puzzle of puzzles) {
    let pmask = 0;

    for (let ch of puzzle) {
      let bit = ch.charCodeAt(0) - "a".charCodeAt(0);
      pmask |= 1 << bit;
    }

    let fch = puzzle[0];
    let wordsToCheck = map.get(fch);
    let count = 0;

    for (let wmask of wordsToCheck) {
      if ((wmask & pmask) === wmask) {
        count++;
      }
    }

    res.push(count);
  }

  return res;
};
```

###### Time and Space Complexity

Time Complexity: **O(N \* L + P \* (6 + 2&#8310;)) = O(N \* L + P)**.

- N \* L for generating masks for each word
- P \* 6 for generating masks for each puzzle
- P \* 2&#8310; for Generating number of subsets. (Note: we are only using 6 chars for finding subsets as we have exlcuded the first char from subsets)

Space Complexity: **O(N)** -- Required for the HashMap. It will contain upto O(N) keys and values.

Where:

- N -- Number of Words
- L -- Average length of each word
- P -- Number of puzzles. (As per input constraints, Length of each puzzle is 7)
