Boolean Parenthesization
Solve this ProblemT for True, F for False) with operators (&, |, ^ for AND, OR, XOR) — for example "T|T&F". Count how many distinct ways to fully parenthesize the expression make it evaluate to True.
The number of parenthesizations of an n-symbol expression grows the same way binary tree shapes do — far too many to enumerate directly once n gets past single digits. The way out is to stop asking "what's the final value" and instead ask two questions about every stretch of the expression at once: in how many ways can it read True, and in how many ways can it read False? Knowing both counts for two adjacent stretches is exactly what's needed to combine them correctly through whichever operator joins them — AND only succeeds when both sides do, OR fails only when both sides do, and XOR succeeds on exactly the two "mismatched" combinations. Building those True/False pairs from the smallest stretches (single symbols) up to the whole expression means every stretch is only ever solved once.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of boolean symbols in expr ≤ 8 - ◆
expr alternates T/F symbols with &, |, ^ operators, and always starts and ends with a symbol (e.g. "T|T&F") - ◆
the answer always fits comfortably in a normal 32-bit int at this size — no modulo needed
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursion Without Memoization
BruteSplit the symbols out from the operators first. Then, for any stretch of the expression, the very last operator applied is whichever one sits at the top of that stretch's parse tree — everything to its left forms one independent sub-expression, everything to its right forms another. Trying every operator in the stretch as that "last one applied" and asking two questions about each side — how many ways can it be True, and how many ways can it be False — is enough to combine them correctly for &, |, and ^. The catch is that the same stretch gets re-asked "how many True ways / how many False ways" over and over through different outer splits, and neither answer is cached.
O(4ⁿ) (Catalan-number growth)O(n)1class Solution {
2 private char[] symbols;
3 private char[] ops;
4
5 public int countWays(String expr) {
6 List<Character> syms = new ArrayList<>();
7 List<Character> operators = new ArrayList<>();
8 for (char c : expr.toCharArray()) {
9 if (c == 'T' || c == 'F') syms.add(c);
10 else operators.add(c);
11 }
12 symbols = new char[syms.size()];
13 for (int i = 0; i < syms.size(); i++) symbols[i] = syms.get(i);
14 ops = new char[operators.size()];
15 for (int i = 0; i < operators.size(); i++) ops[i] = operators.get(i);
16 return solve(0, symbols.length - 1, true);
17 }
18
19 private int solve(int i, int j, boolean wantTrue) {
20 if (i == j) {
21 boolean val = symbols[i] == 'T';
22 return (val == wantTrue) ? 1 : 0;
23 }
24 int ways = 0;
25 for (int k = i; k < j; k++) {
26 int leftTrue = solve(i, k, true), leftFalse = solve(i, k, false);
27 int rightTrue = solve(k + 1, j, true), rightFalse = solve(k + 1, j, false);
28 int total = (leftTrue + leftFalse) * (rightTrue + rightFalse);
29 int trueWays;
30 char op = ops[k];
31 if (op == '&') trueWays = leftTrue * rightTrue;
32 else if (op == '|') trueWays = total - leftFalse * rightFalse;
33 else trueWays = leftTrue * rightFalse + leftFalse * rightTrue;
34 ways += wantTrue ? trueWays : (total - trueWays);
35 }
36 return ways;
37 }
38}Optimal — Bottom-Up Interval DP
OptimalSame "last operator applied" idea, but filled bottom-up: keep two tables, T[i][j] and F[i][j], holding how many ways the symbols from i to j can be grouped to read True or False. Every single symbol is a length-1 base case (1 way to be its own value, 0 ways to be the other). For a longer stretch, try each operator inside it as the final split, combine the two sides' True/False counts through that operator's truth table, and add the result into the running totals. Once every shorter stretch is filled, each longer stretch's answer is built once from stretches already fully solved — nothing is ever recomputed.
O(n³)O(n²)1class Solution {
2 public int countWays(String expr) {
3 List<Character> syms = new ArrayList<>();
4 List<Character> operators = new ArrayList<>();
5 for (char c : expr.toCharArray()) {
6 if (c == 'T' || c == 'F') syms.add(c);
7 else operators.add(c);
8 }
9 int n = syms.size();
10 long[][] T = new long[n][n];
11 long[][] F = new long[n][n];
12 for (int i = 0; i < n; i++) {
13 T[i][i] = syms.get(i) == 'T' ? 1 : 0;
14 F[i][i] = syms.get(i) == 'F' ? 1 : 0;
15 }
16 for (int len = 2; len <= n; len++) {
17 for (int i = 0; i + len - 1 < n; i++) {
18 int j = i + len - 1;
19 long t = 0, f = 0;
20 for (int k = i; k < j; k++) {
21 char op = operators.get(k);
22 long lt = T[i][k], lf = F[i][k], rt = T[k + 1][j], rf = F[k + 1][j];
23 long total = (lt + lf) * (rt + rf);
24 long subT;
25 if (op == '&') subT = lt * rt;
26 else if (op == '|') subT = total - lf * rf;
27 else subT = lt * rf + lf * rt;
28 t += subT;
29 f += total - subT;
30 }
31 T[i][j] = t; F[i][j] = f;
32 }
33 }
34 return (int) T[0][n - 1];
35 }
36}