Count Number of Max Bitwise-OR Subsets

🎯

Count Number of Max Bitwise-OR Subsets

mediumBACKTRACKINGAmazonGoogle

Imagine you have a collection of gadgets, each with a unique set of features represented as bits. You want to find out how many combinations of these gadgets together unlock the maximum possible feature set.

💡 This problem asks you to explore all subsets of a list and compute a bitwise OR for each subset. Beginners often struggle because the number of subsets grows exponentially, and they may not immediately see how to efficiently count subsets achieving the maximum OR value without enumerating all subsets naively.

📋

Problem Statement

Given an integer array nums, return the number of non-empty subsets of nums such that the bitwise OR of all elements in the subset is equal to the maximum possible bitwise OR of any subset of nums. Input: An integer array nums. Output: An integer representing the count of subsets with the maximum bitwise OR.

1 ≤ nums.length ≤ 161 ≤ nums[i] ≤ 10^5

💡

Example

Input"[3,1]"

Output2

The maximum bitwise OR is 3. The subsets with OR=3 are [3] and [3,1].

Input"[2,2,2]"

Output7

All non-empty subsets have OR=2, so count is 2^3 - 1 = 7.

• Single element array → output is 1
• All elements are zero → output is 2^n - 1 (all subsets except empty)
• All elements are the same non-zero number → output is 2^n - 1
• Array with distinct powers of two → output is 1 (only full set)

⚠️

Common Mistakes

Counting empty subset as valid

Output is incorrect because empty subset OR is zero and usually not counted

✅ Start subset enumeration from mask=1 or exclude empty subset in recursion base case

Not updating count when a new max OR is found

Count accumulates incorrectly, leading to wrong final answer

✅ Reset count to 1 when a new max OR is found

Pruning incorrectly when current OR is less than max OR but can still reach max OR

Misses valid subsets, resulting in undercount

✅ Only prune when current OR equals max OR or no possibility to improve

Using bitmask iteration without handling large n

Code runs too slowly or crashes due to exponential time

✅ Limit n to ≤16 or use pruning/DP for larger inputs

🧠

Brute Force (Pure Recursion / Backtracking)

💡 This approach exists to build intuition by exploring every subset explicitly. It helps beginners understand the problem's exponential nature and the mechanics of subset generation.

Intuition

Generate all subsets recursively, compute their bitwise OR, track the maximum OR found, and count how many subsets achieve this maximum.

Algorithm

1. Initialize max_or to 0 and count to 0.
2. Use recursion to explore subsets by including or excluding each element.
3. At each leaf (end of recursion), compute the OR of the chosen subset.
4. Update max_or and count accordingly.

💡 The challenge is to systematically explore all subsets without missing any and correctly update the maximum OR and count as you go.

</>

Code

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        self.max_or = 0
        self.count = 0

        def backtrack(i: int, current_or: int):
            if i == len(nums):
                if current_or > self.max_or:
                    self.max_or = current_or
                    self.count = 1
                elif current_or == self.max_or:
                    self.count += 1
                return
            # Include nums[i]
            backtrack(i + 1, current_or | nums[i])
            # Exclude nums[i]
            backtrack(i + 1, current_or)

        backtrack(0, 0)
        return self.count

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.countMaxOrSubsets([3,1]))  # Expected output: 2
    print(sol.countMaxOrSubsets([2,2,2]))  # Expected output: 7

Line Notes

self.max_or = 0Initialize the maximum OR found so far to zero to track the best OR value

self.count = 0Initialize count of subsets achieving max OR to zero

def backtrack(i: int, current_or: int):Recursive helper to explore subsets starting at index i with current OR

if i == len(nums):Base case: all elements considered, time to update max_or and count

if current_or > self.max_or:Found a new maximum OR, reset count to 1

elif current_or == self.max_or:Found another subset matching max OR, increment count

backtrack(i + 1, current_or | nums[i])Include current element in subset and update OR

backtrack(i + 1, current_or)Exclude current element and keep OR unchanged

return self.countReturn the total count of max OR subsets

import java.util.*;

public class Solution {
    private int maxOr = 0;
    private int count = 0;

    public int countMaxOrSubsets(int[] nums) {
        backtrack(nums, 0, 0);
        return count;
    }

    private void backtrack(int[] nums, int index, int currentOr) {
        if (index == nums.length) {
            if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            } else if (currentOr == maxOr) {
                count++;
            }
            return;
        }
        // Include nums[index]
        backtrack(nums, index + 1, currentOr | nums[index]);
        // Exclude nums[index]
        backtrack(nums, index + 1, currentOr);
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countMaxOrSubsets(new int[]{3,1})); // Expected: 2
        System.out.println(sol.countMaxOrSubsets(new int[]{2,2,2})); // Expected: 7
    }
}

Line Notes

private int maxOr = 0;Store the maximum OR found so far to track best OR value

private int count = 0;Count subsets achieving max OR

if (index == nums.length)Base case: all elements processed

if (currentOr > maxOr)Update max OR and reset count to 1

else if (currentOr == maxOr)Increment count for matching max OR

backtrack(nums, index + 1, currentOr | nums[index]);Include current element in subset

backtrack(nums, index + 1, currentOr);Exclude current element

return;End recursion branch

#include <iostream>
#include <vector>
using namespace std;

class Solution {
    int maxOr = 0;
    int count = 0;

    void backtrack(const vector<int>& nums, int index, int currentOr) {
        if (index == nums.size()) {
            if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            } else if (currentOr == maxOr) {
                count++;
            }
            return;
        }
        // Include nums[index]
        backtrack(nums, index + 1, currentOr | nums[index]);
        // Exclude nums[index]
        backtrack(nums, index + 1, currentOr);
    }

public:
    int countMaxOrSubsets(vector<int>& nums) {
        backtrack(nums, 0, 0);
        return count;
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {3,1};
    cout << sol.countMaxOrSubsets(nums1) << endl; // Expected: 2
    vector<int> nums2 = {2,2,2};
    cout << sol.countMaxOrSubsets(nums2) << endl; // Expected: 7
    return 0;
}

Line Notes

int maxOr = 0;Track maximum OR value found to keep best OR

int count = 0;Count subsets with max OR

if (index == nums.size()) {Base case: all elements considered

if (currentOr > maxOr) {Found new max OR, reset count to 1

else if (currentOr == maxOr) {Increment count for equal max OR

backtrack(nums, index + 1, currentOr | nums[index]);Include current element

backtrack(nums, index + 1, currentOr);Exclude current element

return;End recursion branch

var countMaxOrSubsets = function(nums) {
    let maxOr = 0;
    let count = 0;

    function backtrack(i, currentOr) {
        if (i === nums.length) {
            if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            } else if (currentOr === maxOr) {
                count++;
            }
            return;
        }
        // Include nums[i]
        backtrack(i + 1, currentOr | nums[i]);
        // Exclude nums[i]
        backtrack(i + 1, currentOr);
    }

    backtrack(0, 0);
    return count;
};

// Driver code
console.log(countMaxOrSubsets([3,1])); // Expected: 2
console.log(countMaxOrSubsets([2,2,2])); // Expected: 7

Line Notes

let maxOr = 0;Initialize max OR to zero to track best OR value

let count = 0;Initialize count of max OR subsets

function backtrack(i, currentOr)Recursive function exploring subsets starting at index i

if (i === nums.length)Base case: all elements processed

if (currentOr > maxOr)Update max OR and reset count to 1

else if (currentOr === maxOr)Increment count for subsets matching max OR

backtrack(i + 1, currentOr | nums[i]);Include current element in subset

backtrack(i + 1, currentOr);Exclude current element

⏱

Complexity

TimeO(2^n)

SpaceO(n) due to recursion stack

We explore all subsets (2^n). Each subset requires O(1) OR operations cumulatively during recursion.

💡 For n=16, 2^16 = 65,536 subsets, which is borderline feasible but slow for larger n.

Interview Verdict: Accepted for small n, but inefficient for large inputs

This approach is a baseline to understand the problem but will time out for large inputs due to exponential growth.

🧠

Backtracking with Pruning and Early Max OR Computation

💡 This approach improves brute force by first computing the global max OR, then pruning subsets that cannot reach it, reducing unnecessary recursion.

Intuition

Calculate the maximum OR of the entire array upfront. During recursion, if the current OR combined with remaining elements cannot exceed max OR, prune that branch.

Algorithm

1. Compute max_or by OR-ing all elements.
2. Recursively explore subsets, tracking current OR and index.
3. If current OR equals max_or, increment count and prune further exploration.
4. If current OR combined with remaining elements cannot reach max_or, prune recursion.

💡 Pruning reduces the search space by cutting off branches that can't yield better results, making recursion more efficient.

</>

Code

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        max_or = 0
        for num in nums:
            max_or |= num
        count = 0

        def backtrack(i: int, current_or: int):
            nonlocal count
            if i == len(nums):
                if current_or == max_or:
                    count += 1
                return
            # Prune if current_or already max_or
            if current_or == max_or:
                # All subsets from here will have OR == max_or
                count += 1 << (len(nums) - i)
                return
            # Include nums[i]
            backtrack(i + 1, current_or | nums[i])
            # Exclude nums[i]
            backtrack(i + 1, current_or)

        backtrack(0, 0)
        return count

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.countMaxOrSubsets([3,1]))  # Expected output: 2
    print(sol.countMaxOrSubsets([2,2,2]))  # Expected output: 7

Line Notes

max_or = 0Initialize max OR to zero before computation

for num in nums: max_or |= numCompute global max OR by OR-ing all elements

count = 0Initialize count of subsets with max OR

def backtrack(i: int, current_or: int):Recursive function to explore subsets

if i == len(nums):Base case: all elements considered

if current_or == max_or:If current OR equals max OR, increment count

count += 1 << (len(nums) - i)Add all remaining subsets since OR won't change

backtrack(i + 1, current_or | nums[i])Include current element

backtrack(i + 1, current_or)Exclude current element

public class Solution {
    private int maxOr = 0;
    private int count = 0;

    public int countMaxOrSubsets(int[] nums) {
        for (int num : nums) {
            maxOr |= num;
        }
        backtrack(nums, 0, 0);
        return count;
    }

    private void backtrack(int[] nums, int index, int currentOr) {
        if (index == nums.length) {
            if (currentOr == maxOr) {
                count++;
            }
            return;
        }
        if (currentOr == maxOr) {
            count += 1 << (nums.length - index);
            return;
        }
        backtrack(nums, index + 1, currentOr | nums[index]);
        backtrack(nums, index + 1, currentOr);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countMaxOrSubsets(new int[]{3,1})); // Expected: 2
        System.out.println(sol.countMaxOrSubsets(new int[]{2,2,2})); // Expected: 7
    }
}

Line Notes

for (int num : nums) { maxOr |= num; }Compute max OR of all elements

private void backtrack(int[] nums, int index, int currentOr)Recursive exploration of subsets

if (index == nums.length)Base case: all elements processed

if (currentOr == maxOr)If current OR equals max OR, count all remaining subsets

count += 1 << (nums.length - index);Add count of all subsets from remaining elements

backtrack(nums, index + 1, currentOr | nums[index]);Include current element

backtrack(nums, index + 1, currentOr);Exclude current element

return;End recursion branch

#include <iostream>
#include <vector>
using namespace std;

class Solution {
    int maxOr = 0;
    int count = 0;

    void backtrack(const vector<int>& nums, int index, int currentOr) {
        if (index == nums.size()) {
            if (currentOr == maxOr) {
                count++;
            }
            return;
        }
        if (currentOr == maxOr) {
            count += 1 << (nums.size() - index);
            return;
        }
        backtrack(nums, index + 1, currentOr | nums[index]);
        backtrack(nums, index + 1, currentOr);
    }

public:
    int countMaxOrSubsets(vector<int>& nums) {
        for (int num : nums) maxOr |= num;
        backtrack(nums, 0, 0);
        return count;
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {3,1};
    cout << sol.countMaxOrSubsets(nums1) << endl; // Expected: 2
    vector<int> nums2 = {2,2,2};
    cout << sol.countMaxOrSubsets(nums2) << endl; // Expected: 7
    return 0;
}

Line Notes

for (int num : nums) maxOr |= num;Calculate max OR of all elements

void backtrack(const vector<int>& nums, int index, int currentOr)Recursive subset exploration

if (index == nums.size()) {Base case: all elements processed

if (currentOr == maxOr) {If current OR equals max OR, increment count

count += 1 << (nums.size() - index);Add all subsets from remaining elements

backtrack(nums, index + 1, currentOr | nums[index]);Include current element

backtrack(nums, index + 1, currentOr);Exclude current element

return;End recursion branch

var countMaxOrSubsets = function(nums) {
    let maxOr = 0;
    for (const num of nums) maxOr |= num;
    let count = 0;

    function backtrack(i, currentOr) {
        if (i === nums.length) {
            if (currentOr === maxOr) count++;
            return;
        }
        if (currentOr === maxOr) {
            count += 1 << (nums.length - i);
            return;
        }
        backtrack(i + 1, currentOr | nums[i]);
        backtrack(i + 1, currentOr);
    }

    backtrack(0, 0);
    return count;
};

// Driver code
console.log(countMaxOrSubsets([3,1])); // Expected: 2
console.log(countMaxOrSubsets([2,2,2])); // Expected: 7

Line Notes

for (const num of nums) maxOr |= num;Compute max OR of all elements

let count = 0;Initialize count of max OR subsets

function backtrack(i, currentOr)Recursive function to explore subsets

if (i === nums.length)Base case: all elements processed

if (currentOr === maxOr)If current OR equals max OR, increment count

count += 1 << (nums.length - i);Add all subsets from remaining elements

backtrack(i + 1, currentOr | nums[i]);Include current element

backtrack(i + 1, currentOr);Exclude current element

⏱

Complexity

TimeO(2^n) worst case, but pruning reduces average time

SpaceO(n) recursion stack

Pruning cuts off branches early, but worst case remains exponential. Still better than naive brute force.

💡 For n=16, pruning can significantly reduce explored subsets, improving practical runtime.

Interview Verdict: Accepted and faster than brute force for many inputs

This approach balances simplicity and efficiency, suitable for interview coding.

🧠

Bitmask Enumeration (Iterative Subset Generation)

💡 This approach uses bitmasking to generate all subsets iteratively, which is often faster and easier to implement than recursion for small n.

Intuition

Each subset corresponds to a bitmask from 1 to 2^n - 1. Compute OR for each subset by checking bits and track max OR and count.

Algorithm

1. Initialize max_or to 0 and count to 0.
2. Iterate mask from 1 to 2^n - 1 representing subsets.
3. For each mask, compute OR of elements where bit is set.
4. Update max_or and count accordingly.

💡 This method avoids recursion overhead and uses bit operations to efficiently generate subsets.

</>

Code

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(1, 1 << n):
            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

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.countMaxOrSubsets([3,1]))  # Expected output: 2
    print(sol.countMaxOrSubsets([2,2,2]))  # Expected output: 7

Line Notes

n = len(nums)Store length of input array for bitmask iteration

for mask in range(1, 1 << n):Iterate over all non-empty subsets represented by bitmasks

if mask & (1 << i):Check if ith element is included in current subset

current_or |= nums[i]Update OR with included element

if current_or > max_or:Update max OR and reset count to 1

elif current_or == max_or:Increment count for matching max OR

public class Solution {
    public int countMaxOrSubsets(int[] nums) {
        int n = nums.length;
        int maxOr = 0, count = 0;
        for (int mask = 1; mask < (1 << n); mask++) {
            int currentOr = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    currentOr |= nums[i];
                }
            }
            if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            } else if (currentOr == maxOr) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countMaxOrSubsets(new int[]{3,1})); // Expected: 2
        System.out.println(sol.countMaxOrSubsets(new int[]{2,2,2})); // Expected: 7
    }
}

Line Notes

int n = nums.length;Store length of input array for bitmask iteration

for (int mask = 1; mask < (1 << n); mask++) {Iterate over all non-empty subsets

if ((mask & (1 << i)) != 0)Check if ith element is included in subset

currentOr |= nums[i];Update OR with included element

if (currentOr > maxOr)Update max OR and reset count to 1

else if (currentOr == maxOr)Increment count for matching max OR

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        int n = nums.size();
        int maxOr = 0, count = 0;
        for (int mask = 1; mask < (1 << n); mask++) {
            int currentOr = 0;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    currentOr |= nums[i];
                }
            }
            if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            } else if (currentOr == maxOr) {
                count++;
            }
        }
        return count;
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {3,1};
    cout << sol.countMaxOrSubsets(nums1) << endl; // Expected: 2
    vector<int> nums2 = {2,2,2};
    cout << sol.countMaxOrSubsets(nums2) << endl; // Expected: 7
    return 0;
}

Line Notes

int n = nums.size();Store length of input array for bitmask iteration

for (int mask = 1; mask < (1 << n); mask++) {Iterate over all non-empty subsets

if (mask & (1 << i)) {Check if ith element is included

currentOr |= nums[i];Update OR with included element

if (currentOr > maxOr) {Update max OR and reset count to 1

else if (currentOr == maxOr) {Increment count for matching max OR

var countMaxOrSubsets = function(nums) {
    const n = nums.length;
    let maxOr = 0, count = 0;
    for (let mask = 1; mask < (1 << n); mask++) {
        let currentOr = 0;
        for (let i = 0; i < n; i++) {
            if ((mask & (1 << i)) !== 0) {
                currentOr |= nums[i];
            }
        }
        if (currentOr > maxOr) {
            maxOr = currentOr;
            count = 1;
        } else if (currentOr === maxOr) {
            count++;
        }
    }
    return count;
};

// Driver code
console.log(countMaxOrSubsets([3,1])); // Expected: 2
console.log(countMaxOrSubsets([2,2,2])); // Expected: 7

Line Notes

const n = nums.length;Store length of input array for bitmask iteration

for (let mask = 1; mask < (1 << n); mask++) {Iterate over all non-empty subsets

if ((mask & (1 << i)) !== 0)Check if ith element is included

currentOr |= nums[i];Update OR with included element

if (currentOr > maxOr)Update max OR and reset count to 1

else if (currentOr === maxOr)Increment count for matching max OR

⏱

Complexity

TimeO(n * 2^n)

SpaceO(1) additional space

We iterate over 2^n subsets, and for each subset, we check up to n bits to compute OR.

💡 For n=16, this means about 16 * 65,536 = 1,048,576 operations, which is feasible.

Interview Verdict: Accepted and practical for n ≤ 16

This approach is often preferred in interviews for its clarity and iterative style.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, the pruning backtracking or bitmask iterative approach is best to code due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code due to inefficiency
2. Backtracking with Pruning	O(2^n) worst, better average	O(n) recursion stack	Yes (deep recursion)	N/A	Good to code for efficiency and clarity
3. Bitmask Enumeration	O(n * 2^n)	O(1)	No	N/A	Preferred for small n due to simplicity and no recursion

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, followed by optimizations. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force recursive approach to generate all subsets.Step 3: Explain how to optimize by precomputing max OR and pruning recursion.Step 4: Present the bitmask iterative approach as a clean alternative.Step 5: Discuss time and space complexities and tradeoffs.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of subset generation, bitwise operations, recursion, pruning, and iterative bitmasking. They also check your ability to optimize and reason about complexity.

Common Follow-ups

• What if nums length is up to 10^5? → Use greedy or bitwise tricks, but problem constraints limit n to 16.
• Can you count subsets with OR equal to a given target? → Similar approach but check against target instead of max OR.

💡 Follow-ups test your ability to adapt the solution to larger inputs or variant problems.

🔍

Pattern Recognition

When to Use

1) Problem involves subsets or combinations; 2) Bitwise OR operation is central; 3) Need to count subsets meeting a max condition; 4) Input size small enough for 2^n enumeration.

Signature Phrases

'bitwise OR of all elements in the subset''number of subsets with maximum bitwise OR'

NOT This Pattern When

Problems that require sum or product of subsets, or DP on sequences, are different patterns.

Similar Problems

Maximum XOR of Two Numbers in an Array - uses bitwise operations with subsetsSubsets - classic subset generation problemNumber of Subsets With Bitwise OR Equal to Target - similar counting problem

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. Consider the following Python function that counts subsets with sum K using a space-optimized DP approach. What is the output when called with arr = [1, 2, 3, 3] and K = 6?

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(K, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[K]

print(count_subsets_space_optimized(arr, K))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0,0] since dp[0]=1 and K=6.

2. Step 2: Process each number updating dp

   After processing 1: dp = [1,1,0,0,0,0,0] After 2: dp = [1,1,1,1,0,0,0] After first 3: dp = [1,1,1,2,1,1,1] After second 3: dp = [1,1,1,3,2,2,3]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[6] = 5 subsets sum to 6 [OK]

Hint: Trace dp updates backward to avoid double counting [OK]

Common Mistakes:

• Forgetting to iterate backward in dp array
• Off-by-one errors in dp indices

3. You are given a string containing letters and digits. You need to generate all possible strings by toggling the case of each letter independently, while digits remain unchanged. Which algorithmic approach guarantees generating all valid permutations efficiently?

easy

A. Backtracking with include/exclude choices for each letter's case

B. Sorting the string and then generating permutations by swapping adjacent characters

C. Dynamic programming using a bottom-up table to store partial permutations

D. Greedy algorithm that toggles letters only when it reduces the lexicographical order

Solution

1. Step 1: Understand problem constraints

   The problem requires exploring all combinations of letter cases, which is a classic subsets problem where each letter can be included as lowercase or uppercase.

2. Step 2: Identify suitable algorithm

   Backtracking with include/exclude choices for each letter's case systematically explores all 2^k combinations, ensuring completeness and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all subsets of letter cases [OK]

Hint: Toggle letter cases via backtracking subsets [OK]

Common Mistakes:

• Thinking greedy can find all permutations
• Using DP that doesn't fit subsets pattern

4. What is the time complexity of the optimal backtracking solution for letter case permutation on a string of length n with k letters (non-digit characters)?

medium

A. O(2^k * n) because only letters toggle case and each permutation requires joining n characters

B. O(2^k * k) because only letters are toggled and digits are skipped

C. O(n * 2^n) because each character doubles the permutations

D. O(n^2) because of nested recursion and string concatenation

Solution

1. Step 1: Identify branching factor

   Only letters (k of them) cause branching, each with 2 choices, so total permutations are 2^k.

2. Step 2: Calculate work per permutation

   Each permutation requires joining n characters to form a string, so O(n) per permutation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time is exponential in letters, linear in string length [OK]

Hint: Complexity depends on letters, not total length [OK]

Common Mistakes:

• Assuming all characters double permutations
• Ignoring join cost per permutation

5. What is the time complexity of the optimal bitmask + trie solution for the Number of Valid Words for Each Puzzle problem, given W words with average length L, and P puzzles?

medium

A. O(W * L + P * M), where M is the average number of trie nodes traversed per puzzle

B. O(W * P * L), since each word is checked against each puzzle

C. O(W * 2^7 + P * 7), enumerating all subsets of puzzle letters for each puzzle

D. O(W * L * 26 + P * 26), traversing trie nodes for all letters

Solution

1. Step 1: Analyze word insertion

   Each word is converted to a bitmask and inserted into trie in O(L) time, total O(W * L).

2. Step 2: Analyze puzzle queries

   For each puzzle, dfs traverses trie nodes corresponding to subsets of puzzle letters, average M nodes, total O(P * M).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known optimal complexity [OK]

Hint: Trie traversal depends on subsets of puzzle letters, not all words [OK]

Common Mistakes:

• Assuming brute force complexity
• Confusing 2^7 subsets with trie traversal nodes
• Ignoring average trie traversal cost