Number of Valid Words for Each Puzzle

🎯

Number of Valid Words for Each Puzzle

hardBACKTRACKINGAmazonGoogleFacebook

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.

💡 This problem is about efficiently counting how many words fit specific letter constraints from puzzles. Beginners often struggle because the naive approach involves checking every word against every puzzle, which is too slow. Understanding bitmasking and subset enumeration is key to solving it efficiently.

📋

Problem Statement

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

💡

Example

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

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

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.

• Words with letters not in any puzzle → 0 count
• Puzzles with letters not in any word → 0 count
• Words containing repeated letters → count only once if valid
• Puzzles where first letter is rare → fewer matches

⚠️

Common Mistakes

Not filtering words with more than 7 unique letters

Unnecessary large frequency map and slower subset enumeration

✅ Skip words with unique letter count > 7

Forgetting to include the puzzle's first letter in subset enumeration

Incorrect counts, missing valid words

✅ Always include the first letter bit in subsets when checking frequency

Using string sets instead of bitmasks for subset checks

Slower performance due to repeated set operations

✅ Use integer bitmasks for O(1) subset checks

Enumerating all subsets of puzzle letters including the first letter

Double counting or missing the mandatory first letter condition

✅ Enumerate subsets only of letters excluding the first letter, then add first letter bit

🧠

Brute Force (Check Each Word Against Each Puzzle)

💡 This approach exists to establish a baseline understanding. It is straightforward but inefficient, helping beginners grasp the problem's requirements before optimizing.

Intuition

For each puzzle, check every word to see if it contains the puzzle's first letter and if all letters of the word are in the puzzle.

Algorithm

1. For each puzzle, extract its first letter and the set of letters in the puzzle.
2. For each word, check if it contains the puzzle's first letter.
3. Check if all letters of the word are contained in the puzzle's letters.
4. Count the number of words that satisfy both conditions for each puzzle.

💡 The nested loops and letter checks are easy to understand but lead to a large number of comparisons, making it slow for big inputs.

</>

Code

from typing import List

def findNumOfValidWords(words: List[str], puzzles: List[str]) -> List[int]:
    res = []
    for puzzle in puzzles:
        count = 0
        first = puzzle[0]
        puzzle_set = set(puzzle)
        for word in words:
            if first in word and set(word).issubset(puzzle_set):
                count += 1
        res.append(count)
    return res

# Driver code
if __name__ == "__main__":
    words = ["aaaa","asas","able","ability","actt","actor","access"]
    puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
    print(findNumOfValidWords(words, puzzles))

Line Notes

for puzzle in puzzles:Iterate over each puzzle to compute its valid word count

first = puzzle[0]Store the first letter of the puzzle, a mandatory letter for valid words

puzzle_set = set(puzzle)Convert puzzle letters to a set for quick membership checks

if first in word and set(word).issubset(puzzle_set):Check both conditions: first letter presence and all letters in puzzle

import java.util.*;

public class Solution {
    public static List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        List<Integer> res = new ArrayList<>();
        for (String puzzle : puzzles) {
            int count = 0;
            char first = puzzle.charAt(0);
            Set<Character> puzzleSet = new HashSet<>();
            for (char c : puzzle.toCharArray()) puzzleSet.add(c);
            for (String word : words) {
                if (word.indexOf(first) != -1 && word.chars().allMatch(c -> puzzleSet.contains((char) c))) {
                    count++;
                }
            }
            res.add(count);
        }
        return res;
    }

    public static void main(String[] args) {
        String[] words = {"aaaa","asas","able","ability","actt","actor","access"};
        String[] puzzles = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
        System.out.println(findNumOfValidWords(words, puzzles));
    }
}

Line Notes

for (String puzzle : puzzles)Loop over each puzzle to process

char first = puzzle.charAt(0);Extract the first letter of the puzzle

Set<Character> puzzleSet = new HashSet<>();Store puzzle letters for quick lookup

if (word.indexOf(first) != -1 && word.chars().allMatch(...))Check if word contains first letter and all letters are in puzzle

#include <bits/stdc++.h>
using namespace std;

vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
    vector<int> res;
    for (auto& puzzle : puzzles) {
        int count = 0;
        char first = puzzle[0];
        unordered_set<char> puzzleSet(puzzle.begin(), puzzle.end());
        for (auto& word : words) {
            if (word.find(first) != string::npos) {
                bool valid = true;
                for (char c : word) {
                    if (puzzleSet.find(c) == puzzleSet.end()) {
                        valid = false;
                        break;
                    }
                }
                if (valid) count++;
            }
        }
        res.push_back(count);
    }
    return res;
}

int main() {
    vector<string> words = {"aaaa","asas","able","ability","actt","actor","access"};
    vector<string> puzzles = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
    vector<int> res = findNumOfValidWords(words, puzzles);
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

for (auto& puzzle : puzzles)Iterate over each puzzle

char first = puzzle[0];Store the first letter of the puzzle

unordered_set<char> puzzleSet(puzzle.begin(), puzzle.end());Create a set of puzzle letters for O(1) lookup

if (word.find(first) != string::npos)Check if word contains the puzzle's first letter

function findNumOfValidWords(words, puzzles) {
    const res = [];
    for (const puzzle of puzzles) {
        let count = 0;
        const first = puzzle[0];
        const puzzleSet = new Set(puzzle);
        for (const word of words) {
            if (word.includes(first) && [...word].every(c => puzzleSet.has(c))) {
                count++;
            }
        }
        res.push(count);
    }
    return res;
}

// Driver code
const words = ["aaaa","asas","able","ability","actt","actor","access"];
const puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"];
console.log(findNumOfValidWords(words, puzzles));

Line Notes

for (const puzzle of puzzles)Loop over each puzzle

const first = puzzle[0];Extract the first letter of the puzzle

const puzzleSet = new Set(puzzle);Create a set for quick letter membership checks

if (word.includes(first) && [...word].every(c => puzzleSet.has(c)))Check if word contains first letter and all letters are in puzzle

⏱

Complexity

TimeO(W * P * L) where W = number of words, P = number of puzzles, L = average word length

SpaceO(W * L + P * L) for storing words and puzzles

For each puzzle, we check every word and verify letter conditions, leading to a large nested iteration.

💡 For 10^5 words and 10^4 puzzles, this means 10^9 checks, which is impractical in interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and constraints before optimizing.

🧠

Bitmask + Hash Map Frequency Counting

💡 This approach introduces bitmasking to represent words and puzzles as integers, enabling efficient subset checks and frequency counting.

Intuition

Represent each word as a bitmask of letters. Count frequencies of these masks. For each puzzle, enumerate all subsets of its letters (excluding the first letter) and sum frequencies of valid subsets that include the first letter.

Algorithm

1. Convert each word into a bitmask representing its unique letters and count frequencies in a hashmap.
2. For each puzzle, convert its letters into a bitmask and identify the bitmask of the first letter.
3. Enumerate all subsets of the puzzle's letters excluding the first letter using bitmask subset enumeration.
4. For each subset, add the frequency of the subset combined with the first letter bitmask to the answer.

💡 The key insight is that enumerating subsets of puzzle letters is efficient because puzzles have fixed length 7, so subsets are at most 2^6=64.

</>

Code

from typing import List

def findNumOfValidWords(words: List[str], puzzles: List[str]) -> List[int]:
    freq = {}
    for word in words:
        mask = 0
        for ch in set(word):
            mask |= 1 << (ord(ch) - ord('a'))
        if bin(mask).count('1') <= 7:
            freq[mask] = freq.get(mask, 0) + 1

    res = []
    for puzzle in puzzles:
        first = 1 << (ord(puzzle[0]) - ord('a'))
        mask = 0
        for ch in puzzle[1:]:
            mask |= 1 << (ord(ch) - ord('a'))

        submask = mask
        total = 0
        while True:
            s = submask | first
            if s in freq:
                total += freq[s]
            if submask == 0:
                break
            submask = (submask - 1) & mask
        res.append(total)
    return res

# Driver code
if __name__ == "__main__":
    words = ["aaaa","asas","able","ability","actt","actor","access"]
    puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
    print(findNumOfValidWords(words, puzzles))

Line Notes

for word in words:Iterate over each word to build frequency map

mask |= 1 << (ord(ch) - ord('a'))Set bit corresponding to each unique letter in the word

if bin(mask).count('1') <= 7:Ignore words with more than 7 unique letters since puzzles have 7 letters

while True:Enumerate all subsets of puzzle letters excluding first letter using bitmask subset enumeration

import java.util.*;

public class Solution {
    public static List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (String word : words) {
            int mask = 0;
            for (char c : word.toCharArray()) {
                mask |= 1 << (c - 'a');
            }
            if (Integer.bitCount(mask) <= 7) {
                freq.put(mask, freq.getOrDefault(mask, 0) + 1);
            }
        }

        List<Integer> res = new ArrayList<>();
        for (String puzzle : puzzles) {
            int first = 1 << (puzzle.charAt(0) - 'a');
            int mask = 0;
            for (int i = 1; i < 7; i++) {
                mask |= 1 << (puzzle.charAt(i) - 'a');
            }

            int submask = mask;
            int total = 0;
            while (true) {
                int s = submask | first;
                total += freq.getOrDefault(s, 0);
                if (submask == 0) break;
                submask = (submask - 1) & mask;
            }
            res.add(total);
        }
        return res;
    }

    public static void main(String[] args) {
        String[] words = {"aaaa","asas","able","ability","actt","actor","access"};
        String[] puzzles = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
        System.out.println(findNumOfValidWords(words, puzzles));
    }
}

Line Notes

for (String word : words)Build frequency map of word bitmasks

mask |= 1 << (c - 'a');Set bit for each letter in word

if (Integer.bitCount(mask) <= 7)Filter out words with more than 7 unique letters

while (true)Enumerate all subsets of puzzle letters excluding first letter

#include <bits/stdc++.h>
using namespace std;

vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
    unordered_map<int,int> freq;
    for (auto& word : words) {
        int mask = 0;
        unordered_set<char> unique_chars(word.begin(), word.end());
        for (char c : unique_chars) mask |= 1 << (c - 'a');
        if (__builtin_popcount(mask) <= 7) freq[mask]++;
    }

    vector<int> res;
    for (auto& puzzle : puzzles) {
        int first = 1 << (puzzle[0] - 'a');
        int mask = 0;
        for (int i = 1; i < 7; i++) mask |= 1 << (puzzle[i] - 'a');

        int submask = mask;
        int total = 0;
        while (true) {
            int s = submask | first;
            if (freq.count(s)) total += freq[s];
            if (submask == 0) break;
            submask = (submask - 1) & mask;
        }

        res.push_back(total);
    }
    return res;
}

int main() {
    vector<string> words = {"aaaa","asas","able","ability","actt","actor","access"};
    vector<string> puzzles = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
    vector<int> res = findNumOfValidWords(words, puzzles);
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

unordered_map<int,int> freq;Map bitmask to frequency of words

for (char c : unique_chars) mask |= 1 << (c - 'a');Create bitmask for unique letters in word

if (__builtin_popcount(mask) <= 7)Ignore words with more than 7 unique letters

while (true) { ... }Enumerate all subsets of puzzle letters excluding first letter

function findNumOfValidWords(words, puzzles) {
    const freq = new Map();
    for (const word of words) {
        let mask = 0;
        const unique = new Set(word);
        for (const ch of unique) {
            mask |= 1 << (ch.charCodeAt(0) - 97);
        }
        if (countBits(mask) <= 7) {
            freq.set(mask, (freq.get(mask) || 0) + 1);
        }
    }

    function countBits(x) {
        let count = 0;
        while (x) {
            count += x & 1;
            x >>= 1;
        }
        return count;
    }

    const res = [];
    for (const puzzle of puzzles) {
        const first = 1 << (puzzle.charCodeAt(0) - 97);
        let mask = 0;
        for (let i = 1; i < 7; i++) {
            mask |= 1 << (puzzle.charCodeAt(i) - 97);
        }

        let submask = mask;
        let total = 0;
        while (true) {
            const s = submask | first;
            if (freq.has(s)) total += freq.get(s);
            if (submask === 0) break;
            submask = (submask - 1) & mask;
        }
        res.push(total);
    }
    return res;
}

// Driver code
const words = ["aaaa","asas","able","ability","actt","actor","access"];
const puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"];
console.log(findNumOfValidWords(words, puzzles));

Line Notes

for (const word of words)Build frequency map of word bitmasks

mask |= 1 << (ch.charCodeAt(0) - 97);Set bit for each unique letter in word

if (countBits(mask) <= 7)Filter words with more than 7 unique letters

while (true)Enumerate all subsets of puzzle letters excluding first letter

⏱

Complexity

TimeO(W * L + P * 2^6) where W = number of words, P = number of puzzles, L = average word length

SpaceO(W + P) for frequency map and results

Bitmasking compresses word letters and subset enumeration over 6 letters is efficient, drastically reducing checks.

💡 For 10^5 words and 10^4 puzzles, this approach is feasible because 2^6=64 subsets per puzzle is manageable.

Interview Verdict: Accepted

This approach is efficient and practical for interview coding, demonstrating mastery of bitmasking and subset enumeration.

🧠

Bitmask + Trie Optimization (Advanced)

💡 This approach uses a trie data structure to store word bitmasks and prune search space when enumerating puzzle subsets, further optimizing performance.

Intuition

Build a trie where each node represents a letter bit. For each puzzle, traverse the trie only along paths that correspond to puzzle letters and include the first letter, counting valid words efficiently.

Algorithm

1. Build a trie where each path corresponds to a unique combination of letters from words.
2. Each trie node stores the count of words ending at that node.
3. For each puzzle, recursively traverse the trie, only following branches corresponding to puzzle letters.
4. Ensure the first letter of the puzzle is included in the path before counting words.

💡 Trie traversal prunes invalid subsets early, avoiding enumeration of all subsets explicitly.

</>

Code

from typing import List

class TrieNode:
    def __init__(self):
        self.count = 0
        self.children = {}

class Solution:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, mask):
        node = self.root
        for i in range(26):
            bit = (mask >> i) & 1
            if bit:
                if i not in node.children:
                    node.children[i] = TrieNode()
                node = node.children[i]
        node.count += 1

    def dfs(self, node, puzzle_mask, first_bit, has_first):
        res = node.count if has_first else 0
        for i, child in node.children.items():
            if (puzzle_mask & (1 << i)) != 0:
                res += self.dfs(child, puzzle_mask, first_bit, has_first or (i == first_bit))
        return res

    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        for word in words:
            mask = 0
            for ch in set(word):
                mask |= 1 << (ord(ch) - ord('a'))
            if bin(mask).count('1') <= 7:
                self.insert(mask)

        res = []
        for puzzle in puzzles:
            first_bit = ord(puzzle[0]) - ord('a')
            puzzle_mask = 0
            for ch in puzzle:
                puzzle_mask |= 1 << (ord(ch) - ord('a'))
            res.append(self.dfs(self.root, puzzle_mask, first_bit, False))
        return res

# Driver code
if __name__ == "__main__":
    words = ["aaaa","asas","able","ability","actt","actor","access"]
    puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
    sol = Solution()
    print(sol.findNumOfValidWords(words, puzzles))

Line Notes

class TrieNode:Define trie node with count and children

def insert(self, mask):Insert word bitmask into trie by bits set

def dfs(self, node, puzzle_mask, first_bit, has_first):Recursively traverse trie pruning by puzzle letters

res = node.count if has_first else 0Count words only if first letter included in path

import java.util.*;

class TrieNode {
    int count = 0;
    Map<Integer, TrieNode> children = new HashMap<>();
}

public class Solution {
    TrieNode root = new TrieNode();

    void insert(int mask) {
        TrieNode node = root;
        for (int i = 0; i < 26; i++) {
            if (((mask >> i) & 1) == 1) {
                node.children.putIfAbsent(i, new TrieNode());
                node = node.children.get(i);
            }
        }
        node.count++;
    }

    int dfs(TrieNode node, int puzzleMask, int firstBit, boolean hasFirst) {
        int res = hasFirst ? node.count : 0;
        for (Map.Entry<Integer, TrieNode> entry : node.children.entrySet()) {
            int i = entry.getKey();
            TrieNode child = entry.getValue();
            if ((puzzleMask & (1 << i)) != 0) {
                res += dfs(child, puzzleMask, firstBit, hasFirst || i == firstBit);
            }
        }
        return res;
    }

    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        for (String word : words) {
            int mask = 0;
            for (char c : word.toCharArray()) {
                mask |= 1 << (c - 'a');
            }
            if (Integer.bitCount(mask) <= 7) insert(mask);
        }

        List<Integer> res = new ArrayList<>();
        for (String puzzle : puzzles) {
            int firstBit = puzzle.charAt(0) - 'a';
            int puzzleMask = 0;
            for (char c : puzzle.toCharArray()) puzzleMask |= 1 << (c - 'a');
            res.add(dfs(root, puzzleMask, firstBit, false));
        }
        return res;
    }

    public static void main(String[] args) {
        String[] words = {"aaaa","asas","able","ability","actt","actor","access"};
        String[] puzzles = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
        Solution sol = new Solution();
        System.out.println(sol.findNumOfValidWords(words, puzzles));
    }
}

Line Notes

class TrieNode {Trie node with count and children map

void insert(int mask) {Insert word bitmask into trie by bits set

int dfs(TrieNode node, int puzzleMask, int firstBit, boolean hasFirst) {DFS trie pruning by puzzle letters

int res = hasFirst ? node.count : 0;Count words only if first letter included

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
    int count = 0;
    unordered_map<int, TrieNode*> children;
};

class Solution {
    TrieNode* root = new TrieNode();

    void insert(int mask) {
        TrieNode* node = root;
        for (int i = 0; i < 26; i++) {
            if ((mask >> i) & 1) {
                if (!node->children.count(i)) node->children[i] = new TrieNode();
                node = node->children[i];
            }
        }
        node->count++;
    }

    int dfs(TrieNode* node, int puzzleMask, int firstBit, bool hasFirst) {
        int res = hasFirst ? node->count : 0;
        for (auto& [i, child] : node->children) {
            if ((puzzleMask & (1 << i)) != 0) {
                res += dfs(child, puzzleMask, firstBit, hasFirst || i == firstBit);
            }
        }
        return res;
    }

public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        for (auto& word : words) {
            int mask = 0;
            unordered_set<char> unique_chars(word.begin(), word.end());
            for (char c : unique_chars) mask |= 1 << (c - 'a');
            if (__builtin_popcount(mask) <= 7) insert(mask);
        }

        vector<int> res;
        for (auto& puzzle : puzzles) {
            int firstBit = puzzle[0] - 'a';
            int puzzleMask = 0;
            for (char c : puzzle) puzzleMask |= 1 << (c - 'a');
            res.push_back(dfs(root, puzzleMask, firstBit, false));
        }
        return res;
    }
};

int main() {
    vector<string> words = {"aaaa","asas","able","ability","actt","actor","access"};
    vector<string> puzzles = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
    Solution sol;
    vector<int> res = sol.findNumOfValidWords(words, puzzles);
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

struct TrieNode {Trie node with count and children map

void insert(int mask) {Insert word bitmask into trie by bits set

int dfs(TrieNode* node, int puzzleMask, int firstBit, bool hasFirst) {DFS trie pruning by puzzle letters

int res = hasFirst ? node->count : 0;Count words only if first letter included

class TrieNode {
    constructor() {
        this.count = 0;
        this.children = new Map();
    }
}

class Solution {
    constructor() {
        this.root = new TrieNode();
    }

    insert(mask) {
        let node = this.root;
        for (let i = 0; i < 26; i++) {
            if ((mask >> i) & 1) {
                if (!node.children.has(i)) node.children.set(i, new TrieNode());
                node = node.children.get(i);
            }
        }
        node.count++;
    }

    dfs(node, puzzleMask, firstBit, hasFirst) {
        let res = hasFirst ? node.count : 0;
        for (let [i, child] of node.children.entries()) {
            if ((puzzleMask & (1 << i)) !== 0) {
                res += this.dfs(child, puzzleMask, firstBit, hasFirst || i === firstBit);
            }
        }
        return res;
    }

    findNumOfValidWords(words, puzzles) {
        for (const word of words) {
            let mask = 0;
            const unique = new Set(word);
            for (const ch of unique) {
                mask |= 1 << (ch.charCodeAt(0) - 97);
            }
            if (this.countBits(mask) <= 7) this.insert(mask);
        }

        const res = [];
        for (const puzzle of puzzles) {
            const firstBit = puzzle.charCodeAt(0) - 97;
            let puzzleMask = 0;
            for (const ch of puzzle) {
                puzzleMask |= 1 << (ch.charCodeAt(0) - 97);
            }
            res.push(this.dfs(this.root, puzzleMask, firstBit, false));
        }
        return res;
    }

    countBits(x) {
        let count = 0;
        while (x) {
            count += x & 1;
            x >>= 1;
        }
        return count;
    }
}

// Driver code
const words = ["aaaa","asas","able","ability","actt","actor","access"];
const puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"];
const sol = new Solution();
console.log(sol.findNumOfValidWords(words, puzzles));

Line Notes

class TrieNode {Trie node with count and children map

insert(mask) {Insert word bitmask into trie by bits set

dfs(node, puzzleMask, firstBit, hasFirst) {DFS trie pruning by puzzle letters

let res = hasFirst ? node.count : 0;Count words only if first letter included

⏱

Complexity

TimeO(W * L + P * M) where W = number of words, L = average word length, P = number of puzzles, M = trie traversal nodes per puzzle

SpaceO(W * L) for trie storage

Trie pruning reduces subset enumeration overhead by exploring only valid letter paths per puzzle.

💡 This approach is more complex but can be faster in practice when many words share letter subsets.

Interview Verdict: Accepted (Advanced)

This approach is suitable for candidates comfortable with tries and bitmasking, showing advanced optimization skills.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the bitmask + hashmap approach in 95% of interviews for balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(W * P * L)	O(W * L + P * L)	No	N/A	Mention only - never code due to inefficiency
2. Bitmask + Hash Map Frequency Counting	O(W * L + P * 2^6)	O(W + P)	No	N/A	Code this approach for optimal balance
3. Bitmask + Trie Optimization	O(W * L + P * M)	O(W * L)	Yes (deep recursion)	N/A	Mention as advanced optimization if asked

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, starting from brute force and progressing to optimal bitmask solutions. Practice explaining each step clearly.

How to Present

Clarify problem constraints and requirements.Explain brute force approach and its inefficiency.Introduce bitmasking and frequency map optimization.Discuss subset enumeration for puzzles.Optionally mention trie optimization if time permits.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Understanding of bitmasking, subset enumeration, pruning techniques, and ability to optimize brute force solutions.

Common Follow-ups

• What if puzzles have more than 7 letters? → Subset enumeration becomes expensive, consider pruning or different data structures.
• Can you optimize space usage? → Use integer bitmasks and avoid storing full strings.

💡 Follow-ups test your ability to adapt the solution to variations and optimize resource usage.

🔍

Pattern Recognition

When to Use

1) You need to check subsets of letters efficiently. 2) There is a mandatory letter constraint. 3) Input size is large, requiring optimization. 4) Bitmasking can represent letter sets.

Signature Phrases

'first letter of the puzzle''all letters of the word are in the puzzle'

NOT This Pattern When

Problems that require substring or subsequence matching without letter set constraints

Similar Problems

Word Squares - also uses backtracking and letter constraintsMaximum XOR of Two Numbers in an Array - bitmasking for optimizationNumber of Matching Subsequences - subset and frequency counting

Practice

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

2. What is the time complexity of the backtracking solution with frequency counting for the Combination Sum (Reuse Allowed) problem, where N is the number of candidates, T is the target, and M is the minimum candidate value?

medium

A. O(N * T) because each candidate is tried once for each target value.

B. O(2^N) because each candidate can be either included or excluded once.

C. O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M.

D. O(T^N) because for each target value, all candidates are tried in all combinations.

Solution

1. Step 1: Identify recursion depth and branching factor

   The recursion depth is roughly T/M because the smallest candidate can be used up to T/M times. At each level, up to N candidates are considered with multiple counts.

2. Step 2: Calculate total number of recursive calls

   Each candidate can be chosen 0 to max_use times, leading to branching factor roughly N^(T/M + 1). This exponential complexity dominates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Exponential branching with depth proportional to T/M matches O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M. [OK]

Hint: Exponential in target divided by smallest candidate [OK]

Common Mistakes:

• Confusing DP complexity with backtracking
• Ignoring exponential branching due to reuse

3. The following code attempts to solve the Matchsticks to Square problem using backtracking with bitmask and memoization. Identify the line containing the subtle bug that can cause incorrect results or infinite recursion.

medium

A. Line with 'if total % 4 != 0: return false' (no divisibility check)

B. Line with 'matchsticks.sort(reverse=true)' (missing sorting causes inefficiency)

C. Line with 'memo[(used_mask, curr_sum, sides_formed)] = false' (incorrect memoization)

D. Line with recursive call 'backtrack(next_mask, next_sum, sides_formed)' missing return statement

Solution

1. Step 1: Identify missing return in recursion

   The recursive call without return means the function ignores successful paths, causing incorrect results or infinite recursion.

2. Step 2: Confirm other lines are correct

   Divisibility check is present, sorting is done, and memoization line is correct for caching failures.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing return in recursive call breaks backtracking correctness [OK]

Hint: Missing return in recursive call breaks correctness [OK]

Common Mistakes:

• Forgetting to return recursive call result
• Skipping divisibility check
• Not sorting before backtracking

4. What is the time complexity of generating all subsets of an array of size n using bitmask enumeration, and why is the common misconception that it is O(2^n) incorrect?

medium

A. O(n^2) because we iterate over n elements twice

B. O(2^n) because there are 2^n subsets

C. O(n * 2^n) because each subset can have up to n elements and we build each subset by checking n bits

D. O(n) because we process each element once

Solution

1. Step 1: Count subsets and subset size

   There are 2^n subsets, and each subset can have up to n elements.

2. Step 2: Analyze bitmask enumeration cost

   For each of the 2^n masks, we check n bits to build the subset, resulting in O(n * 2^n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time depends on both number of subsets and subset size [OK]

Hint: Each subset requires O(n) to build, total O(n*2^n) [OK]

Common Mistakes:

• Ignoring subset size in complexity
• Assuming O(2^n) only
• Confusing with DP complexities

5. Suppose the problem is modified so that elements can be reused multiple times in the subset (i.e., the subset can contain duplicates). Which modification to the algorithm is necessary to correctly find the largest divisible subset under this new constraint?

hard

A. Modify DP to consider all previous elements including i itself, allowing repeated use, and remove early break

B. Switch to a graph cycle detection algorithm to handle repeated elements

C. Use the same DP approach but allow dp[i] to consider dp[i] itself for reuse, enabling cycles

D. Use a greedy approach picking the largest element repeatedly until no more divisible

Solution

1. Step 1: Understand reuse impact

   Allowing reuse means elements can appear multiple times, so dp must consider extending from the same element multiple times.

2. Step 2: Modify DP logic

   DP inner loop must consider j ≤ i (including i itself) and remove early break because sorted order no longer guarantees divisibility breaks.

3. Step 3: Reject incorrect options

   Greedy fails to find longest chain; graph cycle detection is unnecessary; naive DP without modification misses reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP adjusted for reuse and no early break handles duplicates [OK]

Hint: Reuse requires DP to consider self and no early break [OK]

Common Mistakes:

• Using original DP without changes leads to incorrect results
• Trying greedy approach which fails on complex divisibility
• Confusing graph cycles with DP chains