Boolean Parenthesization Problem
Problem Statement
Given a boolean expression consisting of symbols T (True) and F (False), and operators & (AND), | (OR), and ^ (XOR), count the number of ways to parenthesize the expression such that it evaluates to True.
Example:
-
Input:
symbols = "TFT",operators = "|&" -
Expression:
T | F & T -
Output:
2 -
Explanation:
((T|F)&T)= True,(T|(F&T))= False. Only 1 way evaluates to True. (Actual answer depends on the expression.) -
Input:
symbols = "TFF",operators = "^|" -
Expression:
T ^ F | F -
Output:
2 -
Explanation:
((T^F)|F)= True,(T^(F|F))= True. Both evaluate to True.
Noob-Friendly Explanation
Imagine you have a math expression with True, False, and operators like AND, OR, XOR. You can put parentheses anywhere you want to change the order of operations (just like in math, (2+3)*4 is different from 2+(3*4)). You need to count how many different ways of placing parentheses make the whole expression evaluate to True.
Think of it like a puzzle: same ingredients, but different ways of combining them can give different results!
Approach 1: Brute Force (Recursion)
Intuition
Try every possible way to split the expression at each operator. For each split, recursively count the number of ways the left part can be True/False and the right part can be True/False, then combine based on the operator.
Algorithm
- For each operator position, split the expression.
- Recursively compute True/False counts for left and right parts.
- Based on the operator, compute how many combinations give True.
class Solution {
public int countWays(String symbols, String operators) {
return solve(symbols, operators, 0, symbols.length() - 1, true);
}
private int solve(String sym, String ops, int i, int j, boolean wantTrue) {
if (i == j) {
if (wantTrue) return sym.charAt(i) == 'T' ? 1 : 0;
else return sym.charAt(i) == 'F' ? 1 : 0;
}
int ways = 0;
// Try each operator position between i and j
for (int k = i; k < j; k++) {
int leftTrue = solve(sym, ops, i, k, true);
int leftFalse = solve(sym, ops, i, k, false);
int rightTrue = solve(sym, ops, k + 1, j, true);
int rightFalse = solve(sym, ops, k + 1, j, false);
char op = ops.charAt(k);
if (op == '&') {
if (wantTrue) ways += leftTrue * rightTrue;
else ways += leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse;
} else if (op == '|') {
if (wantTrue) ways += leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue;
else ways += leftFalse * rightFalse;
} else if (op == '^') {
if (wantTrue) ways += leftTrue * rightFalse + leftFalse * rightTrue;
else ways += leftTrue * rightTrue + leftFalse * rightFalse;
}
}
return ways;
}
}Complexity Analysis
- Time Complexity: O(4^n) - Each split creates overlapping subproblems with exponential growth.
- Space Complexity: O(n) - Recursion stack depth.
Approach 2: Optimal (Dynamic Programming)
Intuition
Use two 2D DP tables: dpTrue[i][j] = number of ways to parenthesize symbols i to j to get True, and dpFalse[i][j] for False. Fill these bottom-up for increasing subexpression lengths.
Algorithm
- Base case: single symbol —
dpTrue[i][i] = 1ifT, elsedpFalse[i][i] = 1. - For each subexpression length, try each operator as the split point.
- Compute True/False counts based on operator rules.
class Solution {
public int countWays(String symbols, String operators) {
int n = symbols.length();
long MOD = 1000000007;
long[][] dpTrue = new long[n][n];
long[][] dpFalse = new long[n][n];
// Base case: single symbols
for (int i = 0; i < n; i++) {
if (symbols.charAt(i) == 'T') {
dpTrue[i][i] = 1;
dpFalse[i][i] = 0;
} else {
dpTrue[i][i] = 0;
dpFalse[i][i] = 1;
}
}
// Fill for increasing lengths
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
dpTrue[i][j] = 0;
dpFalse[i][j] = 0;
for (int k = i; k < j; k++) {
long lt = dpTrue[i][k];
long lf = dpFalse[i][k];
long rt = dpTrue[k + 1][j];
long rf = dpFalse[k + 1][j];
char op = operators.charAt(k);
if (op == '&') {
dpTrue[i][j] = (dpTrue[i][j] + lt * rt) % MOD;
dpFalse[i][j] = (dpFalse[i][j] + lt * rf + lf * rt + lf * rf) % MOD;
} else if (op == '|') {
dpTrue[i][j] = (dpTrue[i][j] + lt * rt + lt * rf + lf * rt) % MOD;
dpFalse[i][j] = (dpFalse[i][j] + lf * rf) % MOD;
} else if (op == '^') {
dpTrue[i][j] = (dpTrue[i][j] + lt * rf + lf * rt) % MOD;
dpFalse[i][j] = (dpFalse[i][j] + lt * rt + lf * rf) % MOD;
}
}
}
}
return (int) dpTrue[0][n - 1];
}
}Complexity Analysis
- Time Complexity: O(n^3) - Three nested loops (length, start, split point).
- Space Complexity: O(n^2) - Two 2D DP tables of size n×n.