Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count the parenthesizations of a boolean expression (operands T/F joined by &, |, ^) that evaluate to true. It's an interval DP: for each sub-expression i..j, compute BOTH the number of ways it can be true and the number it can be false, splitting at every operator k. Combine the left/right true-and-false counts by the operator's truth table. Base case is a single operand. There are O(n²) intervals × O(n) splits → O(n³) time, O(n²) space. The twist versus Matrix Chain: you must carry true AND false counts, because an operator's true-count depends on the operands' false-counts.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise interval DP, realise you must track BOTH true and false counts per sub-expression (not just true), split at each operator, and combine with the correct truth table.
Where candidates slip
Tracking only the true-count and getting stuck when XOR/OR need the false-count, or splitting at operands instead of operators, or filling the table in plain i,j order so sub-intervals aren't ready.
How to stand out
Say 'I'll carry (ways-true, ways-false) for each interval and split on every operator, combining by its truth table'. Derive each operator's formula from when it yields true, then fill by increasing length and note it's the same skeleton as Matrix Chain / Burst Balloons.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCount parenthesizations evaluating to trueState is an interval [i,j]?NoYes, split on operatorExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Recursion Splitting on Each Operator
1Hint 1Explore hintHide hint
Think about which operator is applied LAST. It splits the expression into a left bracketed part and a right bracketed part, each independent.
2Hint 2Explore hintHide hint
For that last operator you need to know how many ways each side can be true AND how many ways each side can be false — XOR and OR mix them. So define solve(i, j) to return BOTH counts.
3Hint 3Explore hintHide hint
Try every operator k between i and j as the last one. Combine the left (lt, lf) and right (rt, rf) by the operator's truth table, summing over all k. Base: a single operand.
A · Core idea
Define solve(i, j) returning a pair (trueWays, falseWays) — the number of parenthesizations of the sub-expression spanning operands i..j that evaluate to true and to false. The decision is which operator is applied last: pick a split operator k, recursively solve the left part i..k-1 and the right part k+1..j, and combine their true/false counts through k's truth table.
Why you must return both true and false counts. This is the insight that separates this problem from Matrix Chain. Consider XOR: the whole thing is true exactly when the two sides have different values, so trueWays += lt·rf + lf·rt. You literally cannot compute the true-count without the operands' false-counts. OR is false only when both sides are false (falseWays += lf·rf); AND is true only when both are true (trueWays += lt·rt). Carrying a single number would leave you unable to evaluate two of the three operators.
Where the products come from. The left part has lt parenthesizations that are true and lf that are false; the right has rt and rf. Each true-left bracketing can be paired with each true-right bracketing independently, so the number of (left true, right true) combinations is the product lt·rt. Summing the products dictated by the operator's truth table over every split k gives the interval's totals.
Why split on operators, not operands. A parenthesization is a binary tree whose internal nodes are operators; choosing the last-applied operator is choosing the root, which cleanly partitions the operands into a left and right contiguous block. Operators live at odd string indices, so k steps by 2.
Why the base case is a single operand. With i == j there's nothing to bracket: T is (true=1, false=0) and F is (true=0, false=1).
Why we don't ship this. The same sub-expression (i, j) is re-solved under many different outer splits — heavy overlap — and the total number of bracketings is Catalan-exponential. Cache solve(i, j) and it collapses to O(n³).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
expr = "T^F" (operands T,F at indices 0,2; operator ^ at index 1)solve(0,0) = T
single operand
(true=1, false=0)1C · Code with teaching comments
Reference implementation previewprivate static final int MOD = 1003; public int countWays(String expr) { int[] res = solve(expr, 0, expr.length() - 1); return res[0] % MOD; // res[0] = true ways, res[1] = false waysExplore the full codeHide the full code
D · Why it works and complexityO(4ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Two index variables (i, j) describe a contiguous interval, the recursion re-solves the same interval through different roots, and the merge needs a pair of attributes (true and false). Interval state + exponential overlap + a richer merge is the signature of an O(n³) interval DP that carries a tuple.
ComplexityO(4ⁿ) time, O(n) space — Each interval branches into O(n) splits and re-solves overlapping sub-expressions; the number of parenthesizations is the Catalan number (~4ⁿ/n^1.5). Recursion depth is O(n).
E · Edge cases and pitfalls5single operand 'T' — Base case returns (1, 0) → answer 1.Explore edge casesHide edge cases
Edge cases handled
single operand 'T'Base case returns (1, 0) → answer 1.single operand 'F'Base case returns (0, 1) → answer 0.
Pitfalls
- Returning only the true-count — you can't evaluate XOR or OR without the false-count.
- Stepping k by 1 — lands on operands; operators are at odd indices, so step by 2.
- Skipping this approach — verbalising the split-on-operator recurrence is exactly what the interviewer wants.
Approach 2 of 3
Top-Down Memoization on (i, j)
1Hint 1Explore hintHide hint
solve(i, j) returns the same pair every call. Where can you store the (true, false) counts so each interval is computed once?
2Hint 2Explore hintHide hint
Use a 2-D memo of pairs (or two 2-D arrays) indexed by interval endpoints i and j. Check on entry, fill before returning.
3Hint 3Explore hintHide hint
There are O(n²) intervals and each scans O(n) operators → O(n³). The memo is O(n²).
A · Core idea
Keep the split-on-operator recurrence but cache the (trueWays, falseWays) pair for each interval (i, j) so every sub-expression is solved exactly once.
The mental shift: an interval's counts depend only on its endpoints. No matter which outer splits led you to consider operands i..j, the number of true and false parenthesizations of that contiguous block is fixed. Caching by (i, j) collapses all the duplicated subtrees. There are O(n²) intervals and each costs O(n) to resolve (scan its operators), giving the O(n³) bound directly.
Why the state is two indices. Like Matrix Chain, an interval needs both a left and right boundary; different ranges have different sub-expressions and therefore different counts. The cache is 2-D, and each cell stores a pair, not a single number.
Sentinel for 'uncomputed'. Use a null entry (Java) or a missing key (Python) to mark untouched intervals — a real count of 0 is valid, so you can't use 0 as 'empty'.
A language note (Java memo vs Python tabulation). Recursion here nests up to O(n) deep, where n is the operand count. For typical expressions (tens of operands) that's harmless in both languages. But Python's default recursion limit is about 1000 and per-call overhead is higher, so for unusually long expressions the bottom-up table (next approach) is the safer default — it visits intervals in a guaranteed-ready order with no recursion stack. In Java, top-down memoization is perfectly comfortable at these sizes.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
expr = "T|F"memo[0][0] = T
(1, 0)
cached1C · Code with teaching comments
Reference implementation previewprivate static final int MOD = 1003; public int countWays(String expr) { int n = expr.length(); int[][][] memo = new int[n][n][]; // memo[i][j] == null until computedExplore the full codeHide the full code
D · Why it works and complexityO(n³) timeO(n²) spaceOpen the invariant and proofExplore the proofHide the proof
Same mechanical DP upgrade as always: a correct recurrence plus a cache keyed on the true state — here the interval (i, j), with a pair of values cached because the merge consumes two attributes. The thinking was done in the brute force; memoization is bookkeeping.
ComplexityO(n³) time, O(n²) space — O(n²) distinct intervals (i, j), each doing O(n) work over split operators → O(n³). The memo holds a pair per interval → O(n²) space; recursion depth is O(n).
E · Edge cases and pitfalls5expr with all '&' — True only when every operand is true; memo collapses many splits to the same counts.Explore edge casesHide edge cases
Edge cases handled
expr with all '&'True only when every operand is true; memo collapses many splits to the same counts.two operandsOne split k; the single operator's truth table gives the pair directly.
Pitfalls
- Using 0 as the 'uncomputed' sentinel — 0 is a legitimate count; use null / a missing key.
- Caching only the true-count — the false-count must be cached too for the merge.
- Very long expressions in Python can approach the recursion limit; tabulation avoids the stack.
Approach 3 of 3 · Optimal
Bottom-Up — Interval DP by Increasing Length (Optimal)
1Hint 1Explore hintHide hint
The counts for interval [i, j] need the counts of strictly shorter intervals [i, k-1] and [k+1, j]. So solve all length-1 intervals (single operands), then longer ones.
2Hint 2Explore hintHide hint
Keep two tables T[i][j] and F[i][j]. Initialise the diagonal from each operand, then for each interval length fill by trying every operator split.
3Hint 3Explore hintHide hint
T[0][n-1] is the answer. Apply the modulus as you accumulate so values stay small.
A · Core idea
Build two tables, T[i][j] and F[i][j], by increasing interval length so every sub-expression is finalised before it's needed. Seed the diagonal from the operands: T[i][i] = 1, F[i][i] = 0 for T, and the reverse for F. Then for each interval (by length), try every operator k as the last-applied one and accumulate the true/false counts via the truth tables. The answer is T[0][n-1].
The mental shift: length is the dependency order. Interval [i, j] depends only on the strictly shorter intervals [i, k-1] and [k+1, j]. Filling by increasing length guarantees both halves are already computed when you reach the merge — no recursion, just nested loops over (length, left endpoint, split operator). This length-ordered fill is the defining move of interval DP; plain row-major iteration would read cells that aren't ready.
Re-deriving the merge in table terms. At split operator k, the left interval [i, k-1] contributes (T[i][k-1], F[i][k-1]) and the right [k+1, j] contributes (T[k+1][j], F[k+1][j]). Multiply and sum per the operator: AND adds T·T to true and the other three products to false; OR adds F·F to false and the rest to true; XOR adds the cross terms T·F + F·T to true and the like terms to false.
Why the diagonal is the base. A length-1 interval is a single operand whose true/false counts are fixed. Every larger interval's counts are anchored on these.
Why two tables, not one. The merge consumes both true and false counts of each half, so both must be stored. This is the only structural difference from Matrix Chain, which stores a single cost per interval.
The modulus. The classic variant reduces the count modulo 1003; apply it on every accumulation so intermediate products never overflow.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
expr = "T|T&F" (operands T,T,F; operators |,&)Interactive diagram
Interval DP fill order by operand span
length 1Single operands seed the diagonal; longer spans combine two ready halves at each operator split. Answer at T[0][n-1].
3C · Code with teaching comments
D · Why it works and complexityO(n³) timeO(n²) spaceOpen the invariant and proofExplore the proofHide the proof
This is the Matrix Chain template with a two-component state: state = contiguous interval, decision = the last operator k, fill order = increasing length — but you carry (true, false) instead of a single cost. Swap the merge rule and the same skeleton counts BST shapes (Unique BSTs), scrambled strings, and polygon triangulations.
ComplexityO(n³) time, O(n²) space — O(n²) intervals × O(n) splits → O(n³) time. Two (n×n) tables → O(n²) space, with no recursion stack.
E · Edge cases and pitfalls6single operand — Length loop never runs; T[0][0] (or F) set by the seed → answer 1 or 0.Explore edge casesHide edge cases
Edge cases handled
single operandLength loop never runs; T[0][0] (or F) set by the seed → answer 1 or 0.expr = "T^T^F"Both bracketings evaluate false → T[0][n-1] = 0.all operands 'T' with '&'Every parenthesization is true → T[0][n-1] equals the Catalan number mod 1003.
Pitfalls
- Iterating i, j in plain order instead of by length — reads T[i][k-1] / T[k+1][j] before they're filled.
- Forgetting one operator's false formula — the three operators have distinct truth tables.
- Skipping the modulus inside the loop — products overflow before the final mod.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewprivate static final int MOD = 1003; public int countWays(String expr) { int n = expr.length(); int[][] T = new int[n][n];Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Carrying only the true-count
XOR is true when the sides differ (lt·rf + lf·rt) and OR is false only when both are false (lf·rf). Without the false-counts you cannot evaluate two of the three operators.
Explore the code comparisonHide the code comparison
Carrying only the true-count
XOR is true when the sides differ (lt·rf + lf·rt) and OR is false only when both are false (lf·rf). Without the false-counts you cannot evaluate two of the three operators.
Don't write this
def solve(i, j):
# returns only ways-to-be-true
...
true_ways += lt * rt # works for & only, breaks for ^ and |Write this instead
def solve(i, j):
# returns (ways_true, ways_false)
...
true_ways += lt * rf + lf * rt # ^ needs the false-counts2Wrong split granularity
Operators sit at odd indices and operands at even. Stepping k by 1 lands on operands and the merge reads garbage. Step k by 2 starting at i+1.
Explore the code comparisonHide the code comparison
Wrong split granularity
Operators sit at odd indices and operands at even. Stepping k by 1 lands on operands and the merge reads garbage. Step k by 2 starting at i+1.
Don't write this
for (int k = i + 1; k < j; k++) { // hits operands tooWrite this instead
for (int k = i + 1; k < j; k += 2) { // operator positions only3Table filled in i,j order, not by length
T[i][j] reads T[i][k-1] and T[k+1][j], which are shorter intervals. Iterating i,j ascending visits [i,j] before some shorter spans are done, reading stale zeros. Fill by increasing length.
Explore the code comparisonHide the code comparison
Table filled in i,j order, not by length
T[i][j] reads T[i][k-1] and T[k+1][j], which are shorter intervals. Iterating i,j ascending visits [i,j] before some shorter spans are done, reading stale zeros. Fill by increasing length.
Don't write this
for i in range(0, n, 2):
for j in range(i + 2, n, 2): # length not controlled
for k in range(i + 1, j, 2):
...Write this instead
for length in range(2, n, 2):
for i in range(0, n - length, 2):
j = i + length
for k in range(i + 1, j, 2):
...Revise
Carry the pattern into the interview
Pattern to remember
Interval DP carrying (trueWays, falseWays); split at every operator
Code pattern to memorize
T(i,i),F(i,i) from the single operand
for each operator k in i+1..j-1 (step 2):
lt,lf = T(i,k-1),F(i,k-1)
rt,rf = T(k+1,j),F(k+1,j)
'&': true += lt*rt; false += lt*lf+lf*rt+lf*rf
'|': true += lt*rt+lt*rf+lf*rt; false += lf*rf
'^': true += lt*rf+lf*rt; false += lt*rt+lf*rf
answer = T(0, n-1)Rules to remember
- 1Carry both true-count and false-count per interval — an operator's true-ways need the operands' false-ways (e.g. XOR is true when the two sides differ).
- 2Split at every operator position
k, not every index; operands sit at even indices, operators at odd ones. - 3Combine the two halves with the operator's truth table: AND true needs both true, OR false needs both false, XOR true needs them different.
- 4Base case is a single operand:
Tcontributes (true=1, false=0),Fcontributes (true=0, false=1). - 5Fill by increasing interval length (or memoize on
(i, j)) so both sub-intervals are ready before the merge — the defining move of interval DP. Apply the modulus (commonly 1003) as you accumulate.
Use this pattern when
- Count (not just decide) the ways to parenthesize / bracket a sequence to reach a target result
- Combining two adjacent groups depends on more than one attribute of each group (here: true AND false counts)
- State is a contiguous interval [i, j] and the answer fuses two sub-intervals via an operator
- Splitting at a middle operator decouples the expression into independent left/right halves
Choose another pattern when
- You only need whether it CAN be true (one boolean), not the count → simpler interval DP or even greedy
- Operators are all the same and associative with no parentheses freedom → arithmetic, not DP
- Operands decided independently → linear DP, not interval
- n is large (thousands) → O(n³) may be too slow; the expression is usually short
Interview takeaway
Boolean Parenthesization is Matrix Chain with a richer state: split at every operator, but track true-count AND false-count because the operator's true-ways are built from a mix of both. Carry a tuple, combine by the truth table, fill by interval length. The same template counts BST shapes, scrambled strings, and any 'count the bracketings' problem.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternInterval DP that carries a multi-attribute state. Recognise it when you COUNT parenthesizations toward a target and the merge at each operator needs more than one fact about each half (here true-count AND false-count). Split on the last operator, carry the tuple, fill by increasing length — the Matrix Chain template with a richer cell.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Matrix Chain MultiplicationThe same split-on-k interval DP, but minimising a single cost instead of counting (true, false) pairs.
- Unique Binary Search TreesComing soonCount BST shapes by choosing each root — the same 'count the bracketings' Catalan recurrence.
- Different Ways to Add ParenthesesComing soonEnumerate the actual results of every parenthesization — split on each operator, return value lists.
- Burst BalloonsComing soonInterval DP splitting on the LAST balloon to burst — same skeleton, different merge.