Number of Valid Words for Each Puzzle

📋

Problem

Imagine you have a list of secret words and a set of puzzles, each puzzle containing a set of letters. You want to find out how many words can be formed from each puzzle under certain letter constraints.

You are given a list of words and a list of puzzles. For each puzzle, you need to find the number of words that satisfy the following conditions: (1) The word contains the first letter of the puzzle. (2) Every letter in the word is contained in the puzzle. Return an array of integers where each element is the number of valid words for the corresponding puzzle.

1 ≤ words.length ≤ 10^54 ≤ words[i].length ≤ 501 ≤ puzzles.length ≤ 10^4puzzles[i].length == 7All strings contain only lowercase English lettersEach puzzle contains unique letters

Edge cases: Words with letters not in any puzzle → 0 countPuzzles with letters not in any word → 0 countWords containing repeated letters → count only once if valid

</>

IDE

def findNumOfValidWords(words: list[str], puzzles: list[str]) -> list[int]:public int[] findNumOfValidWords(String[] words, String[] puzzles)vector<int> findNumOfValidWords(vector<string> words, vector<string> puzzles)function findNumOfValidWords(words, puzzles)

def findNumOfValidWords(words, puzzles):
    # Write your solution here
    pass

class Solution {
    public int[] findNumOfValidWords(String[] words, String[] puzzles) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> findNumOfValidWords(vector<string> words, vector<string> puzzles) {
    // Write your solution here
    return {};
}

function findNumOfValidWords(words, puzzles) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [0,0,0,0,0,0]Ignoring the first letter condition of puzzles when counting valid words.✅ Add explicit check that each word contains the puzzle's first letter before subset verification.

Wrong: [6,6,6,6,6,6]Counting words that are not subsets of the puzzle letters or ignoring subset condition.✅ Use bitmask subset check to ensure word letters are subset of puzzle letters.

Wrong: [2]Counting repeated letters in words multiple times or counting duplicates.✅ Use unique letter sets or bitmask per word to count each word once regardless of repeated letters.

Wrong: Timeout or no outputBrute force approach with O(W*P*L) complexity causing TLE on large inputs.✅ Implement bitmask frequency map and subset enumeration to reduce complexity to O(W*L + P*2^6).

✓

Test Cases

Try testing your solution on empty and minimal inputs to ensure base cases are handled.

Consider tricky cases with repeated letters and enforcing the puzzle's first letter condition.

Think about the time complexity and how bitmasking can reduce the search space drastically.

t1_01basic

Input{"words":["aaaa","asas","able","ability","actt","actor","access"],"puzzles":["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]}

Expected[1,1,3,2,4,0]

⏱ Performance - must finish in 2000ms

For puzzle "aboveyz", only "aaaa" is valid because it contains 'a' and all letters are in the puzzle. For "abslute", words "able", "ability", and "actt" are valid, etc.

💡 Check each puzzle's first letter and verify words contain it and are subsets of puzzle letters.

💡 Use bitmasking to represent words and puzzles for efficient subset checks.

💡 Count words whose bitmask is a subset of the puzzle's bitmask and contain the puzzle's first letter.

Why it failed: Basic case failed - likely incorrect subset check or missing first letter condition. Fix by ensuring word bitmask is subset of puzzle bitmask and word contains puzzle[0].

✓ Core logic for subset and first letter condition is correct.

t1_02basic

Input{"words":["apple","plea","plead","ale","lap","pale","peal"],"puzzles":["aelwxyz","aelpxyz","aelqxyz","aelrxyz","aeluxyz"]}

Expected[3,5,0,0,0]

⏱ Performance - must finish in 2000ms

For puzzle "aelwxyz", valid words are "ale", "lap", "pale". For "aelpxyz", valid words include "apple", "plea", "plead", "ale", "pale". Others have no valid words due to missing letters.

💡 Focus on the puzzle's first letter and check word subsets accordingly.

💡 Remember to count each valid word only once even if letters repeat.

💡 Use bitmask frequency map to quickly count valid words per puzzle.

Why it failed: Failed to count correct valid words - likely ignoring first letter or subset condition. Fix by enforcing puzzle[0] in word and subset bitmask check.

✓ Correctly counts valid words per puzzle using bitmask and first letter condition.

t2_01edge

Input{"words":[],"puzzles":["abcdefg"]}

Expected[0]

⏱ Performance - must finish in 2000ms

Empty words list means no valid words for any puzzle.

💡 Check behavior when words list is empty.

💡 Ensure code handles zero words without errors.

💡 Return zero counts for all puzzles if no words exist.

Why it failed: Fails on empty words input - likely does not handle empty list properly. Fix by adding check for empty words and returning zeros.

✓ Handles empty words input correctly by returning zero counts.

t2_02edge

Input{"words":["a"],"puzzles":["abcdefg"]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single word 'a' contains puzzle's first letter 'a' and is subset of puzzle letters.

💡 Test with single word and puzzle to verify base case.

💡 Check that single letter words are counted if conditions met.

💡 Ensure first letter condition is correctly applied.

Why it failed: Fails single element test - likely missing first letter check or subset logic. Fix by verifying word contains puzzle[0] and is subset.

✓ Correctly counts single word matching puzzle.

t2_03edge

Input{"words":["abcdefg"],"puzzles":["abcdefg"]}

Expected[1]

⏱ Performance - must finish in 2000ms

Word exactly matches puzzle letters and contains first letter.

💡 Test exact boundary where word letters equal puzzle letters.

💡 Check subset condition includes equality.

💡 Ensure first letter condition is enforced.

Why it failed: Fails exact boundary test - likely uses strict subset instead of subset or misses first letter. Fix by using subset or equal check and first letter condition.

✓ Handles exact boundary case correctly.

t3_01corner

Input{"words":["aaaaa","aaaab","aaabb","aabbb","abbbb","bbbbb"],"puzzles":["abxyzwt"]}

Expected[5]

⏱ Performance - must finish in 2000ms

Words with repeated letters count once if valid; all except 'bbbbb' contain 'a' and subset of puzzle letters.

💡 Repeated letters in words should not cause multiple counts.

💡 Use sets or bitmasks to represent unique letters in words.

💡 Count each valid word once regardless of letter repetition.

Why it failed: Fails repeated letters test - likely counts duplicates or ignores first letter. Fix by using unique letter sets and enforcing first letter condition.

✓ Correctly counts words with repeated letters once.

t3_02corner

Input{"words":["abc","bcd","cde","def"],"puzzles":["abcdefg"]}

Expected[1]

⏱ Performance - must finish in 2000ms

Only 'abc' contains puzzle's first letter 'a' and is subset; others do not contain 'a'.

💡 Check that words must contain puzzle's first letter.

💡 Avoid counting words that are subsets but lack first letter.

💡 Verify first letter condition before subset check.

Why it failed: Fails first letter condition test - counts words missing puzzle[0]. Fix by adding explicit check for puzzle[0] in word.

✓ Correctly enforces first letter condition.

t3_03corner

Input{"words":["abc","abcabc","abcabcabc"],"puzzles":["abcdefg"]}

Expected[1]

⏱ Performance - must finish in 2000ms

Multiple occurrences of letters in words do not increase count; only one count per valid word.

💡 Avoid counting multiple occurrences of same word due to repeated letters.

💡 Use unique letter sets or bitmasks for words.

💡 Count each word once regardless of letter repetition.

Why it failed: Fails 0/1 vs unbounded counting - counts repeated letters multiple times. Fix by using unique letter sets or bitmask per word.

✓ Correctly counts each word once despite repeated letters.

t4_01performance

Input{"words":["abcdefg","bcdefgh","cdefghi","defghij","efghijk","fghijkl","ghijklm","hijklmn","ijklmnq","jklmnqr","klmnqrs","lmnqrst","mnopqrst","nopqrstu","opqrstuv","pqrstuvw","qrstuvwx","rstuvwxy","stuvwxyz","tuvwxyzb","uvwxyzbc","vwxyzbcd","wxyzbcde","xyzbcdef","yzbcdefg","zbcdefgh","bcdefgha","cdefghab","defghabc","efghabcd","fghabcde","ghabcdef","habcdefg","abcdefga","bcdefgab","cdefgabc","defgabcd","efgabcdh","fgabcdhi","gabcdhij","abcdhijk","bcdhijkl","cdhijklm","dhijklmn","hijklmno","ijklmnoq","jklmnoqr","klmnoqrs","lmnoqrst","mnoqrstu","noqrstuv","oqrstuvw","qrstuvwx","rstuvwxy","stuvwxyz","tuvwxyzb","uvwxyzbc","vwxyzbc","wxyzbcd","xyzbcdef","yzbcdefg","zbcdefgh","bcdefgha","cdefghab","defghabc","efghabcd","fghabcde","ghabcdef","habcdefg","abcdefga","bcdefgab","cdefgabc","defgabcd","efgabcdh","fgabcdhi","gabcdhij","abcdhijk","bcdhijkl","cdhijklm","dhijklmn","hijklmno","ijklmnoq","jklmnoqr","klmnoqrs","lmnoqrst","mnoqrstu","noqrstuv","oqrstuvw","qrstuvwx","rstuvwxy","stuvwxyz","tuvwxyzb","uvwxyzbc","vwxyzbc","wxyzbcd","xyzbcdef","yzbcdefg","zbcdefgh","bcdefgha","cdefghab"],"puzzles":["abcdefg","bcdefgh","cdefghi","defghij","efghijk","fghijkl","ghijklm","hijklmn","ijklmnq","jklmnqr","klmnqrs","lmnqrst","mnopqrst","nopqrstu","opqrstuv","pqrstuvw","qrstuvwx","rstuvwxy","stuvwxyz","tuvwxyzb","uvwxyzbc","vwxyzbcd","wxyzbcde","xyzbcdef","yzbcdefg","zbcdefgh","bcdefgha","cdefghab","defghabc","efghabcd","fghabcde","ghabcdef","habcdefg","abcdefga","bcdefgab","cdefgabc","defgabcd","efgabcdh","fgabcdhi","gabcdhij","abcdhijk","bcdhijkl","cdhijklm","dhijklmn","hijklmno","ijklmnoq","jklmnoqr","klmnoqrs","lmnoqrst","mnoqrstu","noqrstuv","oqrstuvw","qrstuvwx","rstuvwxy","stuvwxyz","tuvwxyzb","uvwxyzbc","vwxyzbc","wxyzbcd","xyzbcdef","yzbcdefg","zbcdefgh","bcdefgha","cdefghab","defghabc","efghabcd","fghabcde","ghabcdef","habcdefg","abcdefga","bcdefgab","cdefgabc","defgabcd","efgabcdh","fgabcdhi","gabcdhij","abcdhijk","bcdhijkl","cdhijklm","dhijklmn","hijklmno","ijklmnoq","jklmnoqr","klmnoqrs","lmnoqrst","mnoqrstu","noqrstuv","oqrstuvw","qrstuvwx","rstuvwxy"]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 words and 100 puzzles at constraint boundary; O(W*P*L) brute force will TLE; efficient bitmask + hashmap needed.

💡 Brute force checking each word against each puzzle is too slow.

💡 Use bitmask representation and frequency map of words.

💡 Enumerate subsets of puzzle letters excluding first letter to count valid words efficiently.

Why it failed: TLE on large input - brute force O(W*P*L) too slow. Fix by implementing bitmask + hashmap frequency counting with subset enumeration.

✓ Efficient bitmask + hashmap approach confirmed by passing performance test.

Practice

1. You are given an array of positive integers and a target sum K. You need to find how many subsets of the array sum exactly to K. Which of the following approaches guarantees an optimal solution with polynomial time complexity?

easy

A. Greedy algorithm that picks the largest elements first until the sum reaches or exceeds K

B. Pure recursion that tries all subsets without memoization

C. Dynamic Programming using a bottom-up tabulation approach that counts subsets for all sums up to K

D. Sorting the array and using two pointers to find pairs that sum to K

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all subsets summing to K, which involves exploring combinations, not just pairs or greedy picks.

2. Step 2: Evaluate approaches

   Greedy and two-pointer methods fail because they do not consider all subsets. Pure recursion is correct but exponential. Bottom-up DP efficiently counts subsets for all sums up to K, ensuring polynomial time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP tabulation counts subsets for all sums -> polynomial time [OK]

Hint: Counting subsets with sum K requires DP, not greedy or two-pointer [OK]

Common Mistakes:

• Assuming greedy or two-pointer works for subset sums
• Confusing counting subsets with finding pairs

2. You are given a set of sticks with various lengths. The goal is to determine if these sticks can be arranged to form a perfect square, using all sticks exactly once. Which algorithmic approach is most suitable to guarantee an optimal solution for this problem?

easy

A. Backtracking with bitmasking and memoization to explore all subsets efficiently while pruning invalid paths.

B. Greedy algorithm that always picks the longest stick first and tries to form sides sequentially.

C. Dynamic programming based on subset sums without pruning or memoization.

D. Simple brute force recursion that tries all possible assignments of sticks to sides without optimization.

Solution

1. Step 1: Understand problem constraints

   The problem requires using all sticks exactly once to form four equal sides, which is a partitioning problem with strict constraints.

2. Step 2: Identify suitable algorithm

   Greedy approaches fail because local choices don't guarantee global feasibility. Simple brute force is correct but inefficient. DP without pruning is too slow. Backtracking with bitmask and memoization efficiently explores subsets and prunes invalid paths, guaranteeing optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask + memoization prunes repeated states [OK]

Hint: Bitmask + memoization prunes repeated states [OK]

Common Mistakes:

• Assuming greedy always works for partitioning
• Confusing DP without pruning as efficient
• Ignoring memoization benefits

3. You are given an integer array that may contain duplicates. Your task is to find all possible subsets without duplicate subsets in the result. Which approach guarantees generating all unique subsets efficiently without redundant computations?

easy

A. Generate all subsets using brute force recursion and then filter duplicates by storing subsets in a hash set.

B. Use a greedy algorithm that picks elements only if they are not duplicates of the previous element.

C. Use dynamic programming with a 2D table tracking subset sums to avoid duplicates.

D. Sort the array and use backtracking with skipping duplicates at the same recursion depth to avoid repeated subsets.

Solution

1. Step 1: Understand the problem constraints

   The problem requires generating all unique subsets from an array that may contain duplicates, avoiding duplicate subsets in the output.

2. Step 2: Identify the approach that handles duplicates efficiently

   Sorting the array groups duplicates together, allowing the backtracking algorithm to skip duplicates at the same recursion level, preventing repeated subsets without extra filtering.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking with sorting and skipping duplicates is the standard pattern for Subsets II [OK]

Hint: Sort and skip duplicates at recursion level [OK]

Common Mistakes:

• Using greedy approach misses some subsets
• DP approach is unrelated to subset generation here
• Brute force with set filtering is inefficient

4. Identify the bug in the following code snippet for counting max bitwise-OR subsets:

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_or = 0
        count = 0
        for mask in range(0, 1 << n):  # Note: starts from 0
            current_or = 0
            for i in range(n):
                if mask & (1 << i):
                    current_or |= nums[i]
            if current_or > max_or:
                max_or = current_or
                count = 1
            elif current_or == max_or:
                count += 1
        return count

medium

A. The count variable should be reset inside the inner loop

B. The OR operation should be replaced with AND

C. The loop should start from 1 to exclude empty subset

D. max_or should be initialized to -1 instead of 0

Solution

1. Step 1: Identify that mask=0 represents empty subset

   Empty subset OR is 0, which is usually not counted as a valid subset.

2. Step 2: Recognize that including empty subset inflates count incorrectly

   Starting from mask=0 causes counting empty subset, leading to wrong final count.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Exclude empty subset by starting mask from 1 -> correct counting [OK]

Hint: Empty subset mask=0 must be excluded to avoid incorrect counts [OK]

Common Mistakes:

• Counting empty subset as valid
• Incorrect initialization of max_or

5. The following code attempts to generate all unique subsets from an array with duplicates. Which line contains a subtle bug that causes incorrect or duplicate subsets?

medium

A. Line 9: if i > 0 and nums[i] == nums[i - 1]: s = 0

B. Line 13: res.append(res[j] + [nums[i]])

C. Line 11: start = len(res)

D. Line 6: nums.sort()

Solution

1. Step 1: Understand the role of variable s

   Variable s determines the start index for adding new subsets. For duplicates, s should be set to the previous start to avoid duplicates.

2. Step 2: Identify the bug in line 9

   Setting s = 0 for duplicates causes subsets to be appended from the beginning, generating duplicate subsets. The correct logic is to set s = start (previous length) to skip duplicates only at the same recursion level.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect s causes duplicate subsets [OK]

Hint: Duplicate skipping must use previous start index [OK]

Common Mistakes:

• Setting s=0 always for duplicates
• Not sorting input before processing
• Appending without proper start index