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 unsorted array of positive integers. Your task is to find the largest subset such that for every pair (Si, Sj) in the subset, either Si divides Sj or Sj divides Si. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Greedy approach by always picking the smallest element and adding divisible elements afterwards

B. Use a brute force backtracking to generate all subsets and check divisibility

C. Sort the array and use dynamic programming to build the longest chain where each element divides the next

D. Use a graph traversal to find the largest clique where edges represent divisibility

Solution

1. Step 1: Understand problem constraints

   The problem requires a subset where every pair is divisible in one direction, which suggests a chain-like structure.

2. Step 2: Identify suitable algorithm

   Sorting the array allows divisibility checks to be done efficiently in increasing order, enabling dynamic programming to build the longest divisible chain.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting + DP is classic for largest divisible subset [OK]

Hint: Sort + DP builds longest divisible chain [OK]

Common Mistakes:

• Greedy fails because local choices don't guarantee global maximum
• Brute force is correct but inefficient, not practical
• Graph clique approach is incorrect because divisibility is not symmetric

2. Consider the following Python code for finding the largest divisible subset. What is the final returned list when the input is [1, 2, 3]?

from typing import List

def largestDivisibleSubset(nums: List[int]) -> List[int]:
    if not nums:
        return []
    nums.sort()
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    max_index = 0

    for i in range(n):
        for j in range(i - 1, -1, -1):
            if nums[i] % nums[j] == 0:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            else:
                break
        if dp[i] > dp[max_index]:
            max_index = i

    result = []
    while max_index >= 0:
        result.append(nums[max_index])
        max_index = prev[max_index]
    return result[::-1]

print(largestDivisibleSubset([1, 2, 3]))

easy

A. [1, 2]

B. [1, 3]

C. [1, 2, 3]

D. [2, 3]

Solution

1. Step 1: Trace dp and prev arrays

   Sorted nums = [1, 2, 3]. For i=1 (2), dp[1]=2, prev[1]=0 since 2 % 1 == 0. For i=2 (3), dp[2]=2, prev[2]=0 since 3 % 1 == 0 but 3 % 2 != 0 (break early).

2. Step 2: Reconstruct subset from max_index=1 or 2

   dp[1] and dp[2] both 2, max_index updated to 2 last. Reconstruct: nums[2]=3, prev[2]=0 -> nums[0]=1. Result reversed is [1, 3].

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Subset [1,3] is largest divisible subset returned [OK]

Hint: Trace dp and prev arrays carefully [OK]

Common Mistakes:

• Assuming [1,2,3] all divisible chain without checking divisibility
• Confusing indices when reconstructing subset
• Ignoring early break in inner loop

3. What is the time complexity of the iterative lexicographic combinations generation algorithm for generating all combinations of size k from n elements?

medium

A. O(n^k) because each element can be chosen or not

B. O(k * (n choose k)) since each combination of size k is generated once and updated in O(k)

C. O(\u03C3(n choose k) * k) where \u03C3 is the number of combinations generated

D. O(n * k) because the outer loop runs n times and inner loop k times

Solution

1. Step 1: Identify number of combinations

   There are exactly (n choose k) combinations to generate.

2. Step 2: Analyze per-combination cost

   Each combination is generated and updated in O(k) time due to copying and resetting elements.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time is proportional to number of combinations times combination size [OK]

Hint: Time depends on number of combinations times k [OK]

Common Mistakes:

• Confusing with exponential O(n^k) or linear O(n*k) complexities

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. Suppose the problem changes: now each element in the input array can be chosen multiple times (unlimited reuse), and duplicates still exist. Which modification to the iterative approach correctly generates all unique subsets with duplicates and unlimited reuse?

hard

A. Keep the same code but remove the duplicate skipping condition to allow reuse.

B. Sort the array, and for each element, always start from index 0 when adding new subsets to allow reuse, but skip duplicates at the same recursion level.

C. Sort the array, and for each element, start from the previous start index for duplicates, but allow reuse by appending to all existing subsets including newly added ones in the same iteration.

D. Use backtracking with a visited array to track reuse and skip duplicates by sorting.

Solution

1. Step 1: Understand unlimited reuse impact

   Unlimited reuse means subsets can include the same element multiple times, so the iteration must consider all existing subsets each time.

2. Step 2: Modify iteration start index

   To allow reuse, always start from index 0 when adding new subsets, so elements can be appended multiple times. However, duplicates must still be skipped at the same recursion level to avoid repeated subsets.

3. Step 3: Confirm skipping duplicates at recursion level

   Skipping duplicates at the same recursion level prevents generating identical subsets multiple times despite reuse.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Starting from 0 allows reuse; skipping duplicates avoids repeats [OK]

Hint: Start from 0 to allow reuse; skip duplicates at recursion level [OK]

Common Mistakes:

• Removing duplicate skipping causes duplicates
• Starting from previous start index blocks reuse
• Using visited array unnecessarily complicates iterative approach