What is the Boolean Parenthesization Problem?
Learn the boolean parenthesization interval DP problem, its true/false table recurrence, and how to answer this interview question.
Expected Interview Answer
The boolean parenthesization problem counts, given a string of boolean operands (T/F) separated by operators (AND, OR, XOR), how many ways parentheses can be inserted so the whole expression evaluates to true, solved with interval dynamic programming that tracks both true-count and false-count for every subexpression.
For an operand range i to j, you try every operator k in between as the last one applied, splitting the expression into a left part i..k and a right part k+1..j; the number of ways the full range evaluates true or false is computed by combining every true/false count of the left part with every true/false count of the right part according to that operator's truth table. This is a matrix-chain-style interval DP with O(n^3) time, where n is the number of operands, since there are O(n^2) intervals each trying O(n) split points. Two parallel tables, trueWays[i][j] and falseWays[i][j], must be maintained simultaneously because an AND, OR, or XOR combination needs to know both true and false counts of its subparts to correctly count outcomes. The final answer is trueWays[0][n-1] for the whole expression.
- Counts all valid parenthesizations without generating them explicitly
- O(n^3) interval DP versus exponential enumeration of parenthesizations
- Tracks both true and false counts simultaneously, needed by every operator
- Generalizes the matrix-chain interval DP pattern to boolean logic
AI Mentor Explanation
A commentator has a sequence of match outcomes (win/loss) joined by conditional connectors (AND/OR/XOR rules for combining storylines) and wants to count how many ways to group the sequence with brackets so the overall storyline reads as a win. For each possible grouping split point, the commentator combines every possible win/loss outcome of the left group with every possible win/loss outcome of the right group according to that connector's rule, tallying both win-counts and loss-counts for every sub-range. Because a connector like XOR needs to know both how many ways the left is a win and how many ways it's a loss to correctly tally the combined outcome, both tallies must be tracked for every sub-range, not just the win tally. This mirrors the boolean parenthesization DP exactly: interval-based counting where every subrange needs both possible outcome counts.
Step-by-Step Explanation
Step 1
Define dual states
trueWays[i][j] and falseWays[i][j] = number of ways operand range i..j evaluates true or false with some parenthesization.
Step 2
Base case
For a single operand i, trueWays[i][i]=1,falseWays[i][i]=0 if operand is T (and vice versa for F).
Step 3
Split on every operator k
For each operator between i and j, combine left (i..k) and right (k+1..j) true/false counts using that operator's truth table.
Step 4
Combine using the operator truth table
e.g. for AND, total true ways = sum over splits of (leftTrue * rightTrue); total false ways = total combos minus true combos.
What Interviewer Expects
- Recognize the need for BOTH true and false counts per interval, not just true
- Correctly derive the combination formula per operator (AND, OR, XOR)
- State the O(n^3) time complexity from O(n^2) intervals times O(n) split points
- Explain the base case for single operands
Common Mistakes
- Tracking only trueWays and trying to derive falseWays incorrectly as “total minus trueWays” per interval without proper combinatorics
- Getting the OR truth-table combination wrong (OR is true unless both sides are false)
- Forgetting XOR requires exactly one side true: leftTrue*rightFalse + leftFalse*rightTrue
- Not memoizing overlapping i..j intervals, causing exponential blowup
Best Answer (HR Friendly)
“The boolean parenthesization problem asks how many different ways you can add parentheses to a string of trues, falses, ANDs, ORs, and XORs so the whole thing evaluates to true. I solve it with dynamic programming over intervals, where for every sub-expression I track not just how many ways it can be true, but also how many ways it can be false, because operators like XOR need both pieces of information to combine correctly.”
Code Example
def count_ways(symbols, operators):
n = len(symbols)
true_ways = [[0] * n for _ in range(n)]
false_ways = [[0] * n for _ in range(n)]
for i in range(n):
if symbols[i] == "T":
true_ways[i][i] = 1
else:
false_ways[i][i] = 1
for length in range(2, n + 1):
for i in range(0, n - length + 1):
j = i + length - 1
for k in range(i, j):
op = operators[k]
lt, lf = true_ways[i][k], false_ways[i][k]
rt, rf = true_ways[k + 1][j], false_ways[k + 1][j]
total = (lt + lf) * (rt + rf)
if op == "AND":
t = lt * rt
elif op == "OR":
t = total - (lf * rf)
else: # XOR
t = lt * rf + lf * rt
true_ways[i][j] += t
false_ways[i][j] += total - t
return true_ways[0][n - 1]Follow-up Questions
- How would you extend this to support NAND or NOR operators?
- How would you memoize this top-down instead of building the table bottom-up?
- Why is the OR combination formula “total minus false*false” rather than a direct sum?
- How does this problem relate to Catalan numbers when there were no operators to choose between?
MCQ Practice
1. Why must both trueWays and falseWays be tracked for every interval?
Every operator's combination formula mixes true and false counts from both sides, so both tables are required throughout.
2. What is the time complexity of the standard boolean parenthesization DP for n operands?
There are O(n^2) intervals, each trying O(n) operator split points, giving O(n^3) total.
3. For an OR operator combining left and right subexpressions, how do you compute trueWays?
OR is false only when both sides are false, so trueWays for OR is total combinations minus the false*false combinations.
Flash Cards
What does the boolean parenthesization problem count? — The number of ways to insert parentheses into a boolean expression so it evaluates to true.
What two tables does the DP maintain per interval? — trueWays[i][j] and falseWays[i][j], since every operator needs both to combine correctly.
What is the time complexity? — O(n^3), from O(n^2) intervals each trying O(n) split points.
How is XOR's trueWays computed from left/right counts? — leftTrue*rightFalse + leftFalse*rightTrue, since XOR is true when exactly one side is true.