Boolean Parenthesization — Solution in Python, Java & C++
Boolean Parenthesization solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Boolean Parenthesization is a hard coding problem on strings and dynamic programming, asked in Amazon, Microsoft, Flipkart and Samsung interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Microsoft, Flipkart, Samsung
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a boolean expression s with no parentheses. Its characters at even positions are operands — 'T' (true) or 'F' (false) — and the characters between them are operators:
'&'— boolean AND'|'— boolean OR'^'— boolean XOR
Count the number of ways to fully parenthesise the expression so that it evaluates to true. Two ways differ if they group the operands differently (equivalently, if the binary trees of operations differ). A single operand needs no parentheses and is counted as one way.
The count grows quickly, so return it modulo 1003.
Example 1
Input: s = "T|T&F^T"
Output: 4
Explanation: ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and (T|((T&F)^T)) are true; the fifth grouping, ((T|(T&F))^T), is false.
Example 2
Input: s = "T^F|F"
Output: 2
Explanation: Both ((T^F)|F) and (T^(F|F)) evaluate to true.
Example 3
Input: s = "F"
Output: 0
Explanation: The only way to read a lone F is false.
Constraints
1 <= s.length <= 199s.length is odds[i] is 'T' or 'F' at even i and one of '&', '|', '^' at odd i
Hints for Boolean Parenthesization
Hint 1
Whatever the parenthesisation, one operator is applied last. It splits the expression into a left part and a right part.
Hint 2
To know how many ways the whole is true you need, for each part, how many ways it is true and how many ways it is false.
Hint 3
Let
T[i][j]andF[i][j]count the true/false groupings of operandsi..j. For a last operator betweenkandk+1, combine the four counts by its truth table, and fill the tables by increasing length.
How to solve Boolean Parenthesization
Choose the operator evaluated last. The groupings of the left operands and of the right operands are independent, so the number of ways the whole is true is a product of left and right counts — but which products depends on the operator, and an AND/XOR/OR result can come from false parts too. So track true and false counts for every interval of operands.
Approach
- Let
mbe the number of operands (operandiiss[2i], the operator after it iss[2i + 1]). SetT[i][i] = 1, F[i][i] = 0for'T'and the reverse for'F'. - For lengths 2..m and every interval
i..j, for every splitkini..j-1with operatorop = s[2k + 1]and countslt, lffori..k,rt, rffork+1..j: &: true +=lt*rt, false +=lt*rf + lf*rt + lf*rf.|: true +=lt*rt + lt*rf + lf*rt, false +=lf*rf.^: true +=lt*rf + lf*rt, false +=lt*rt + lf*rf. Reduce modulo 1003 as you go.- Return
T[0][m - 1].
Why it works
Each full parenthesisation of i..j has exactly one last operator, so splitting on it counts every grouping exactly once. Given that split, a grouping of the whole is a pair (left grouping, right grouping), and its value is the operator applied to their values — hence the products of the matching true/false counts.
Complexity
- Time —
O(m^3) - Space —
O(m^2)
Pitfalls
- Counting only true groupings is not enough:
F | T,F ^ TandT ^ Fneed the false counts of a part. - Operands and operators interleave — operand
iis at index2i, noti. - Products of two residues below 1003 are at most about 10^6, and a split adds three of them, so 32-bit arithmetic is safe if you reduce after each split.
Reference solution
Python
def countWays(s: str) -> int:
MOD = 1003
m = (len(s) + 1) // 2
T = [[0] * m for _ in range(m)]
F = [[0] * m for _ in range(m)]
for i in range(m):
if s[2 * i] == 'T':
T[i][i] = 1
else:
F[i][i] = 1
for length in range(2, m + 1):
for i in range(0, m - length + 1):
j = i + length - 1
t = f = 0
for k in range(i, j):
lt, lf, rt, rf = T[i][k], F[i][k], T[k + 1][j], F[k + 1][j]
op = s[2 * k + 1]
if op == '&':
t += lt * rt
f += lt * rf + lf * rt + lf * rf
elif op == '|':
t += lt * rt + lt * rf + lf * rt
f += lf * rf
else:
t += lt * rf + lf * rt
f += lt * rt + lf * rf
T[i][j] = t % MOD
F[i][j] = f % MOD
return T[0][m - 1]Java
public static int countWays(String s) {
final int MOD = 1003;
int m = (s.length() + 1) / 2;
int[][] T = new int[m][m], F = new int[m][m];
for (int i = 0; i < m; i++) {
if (s.charAt(2 * i) == 'T') T[i][i] = 1; else F[i][i] = 1;
}
for (int len = 2; len <= m; len++) {
for (int a = 0; a + len - 1 < m; a++) {
int b = a + len - 1;
int t = 0, f = 0;
for (int k = a; k < b; k++) {
int lt = T[a][k], lf = F[a][k], rt = T[k + 1][b], rf = F[k + 1][b];
char op = s.charAt(2 * k + 1);
if (op == '&') {
t += lt * rt;
f += lt * rf + lf * rt + lf * rf;
} else if (op == '|') {
t += lt * rt + lt * rf + lf * rt;
f += lf * rf;
} else {
t += lt * rf + lf * rt;
f += lt * rt + lf * rf;
}
t %= MOD;
f %= MOD;
}
T[a][b] = t;
F[a][b] = f;
}
}
return T[0][m - 1];
}C++
int countWays(string s) {
const int MOD = 1003;
int m = (s.size() + 1) / 2;
vector<vector<int>> T(m, vector<int>(m, 0)), F(m, vector<int>(m, 0));
for (int i = 0; i < m; i++) {
if (s[2 * i] == 'T') T[i][i] = 1; else F[i][i] = 1;
}
for (int len = 2; len <= m; len++) {
for (int a = 0; a + len - 1 < m; a++) {
int b = a + len - 1;
int t = 0, f = 0;
for (int k = a; k < b; k++) {
int lt = T[a][k], lf = F[a][k], rt = T[k + 1][b], rf = F[k + 1][b];
char op = s[2 * k + 1];
if (op == '&') {
t += lt * rt;
f += lt * rf + lf * rt + lf * rf;
} else if (op == '|') {
t += lt * rt + lt * rf + lf * rt;
f += lf * rf;
} else {
t += lt * rf + lf * rt;
f += lt * rt + lf * rf;
}
t %= MOD;
f %= MOD;
}
T[a][b] = t;
F[a][b] = f;
}
}
return T[0][m - 1];
}JavaScript
var countWays = function(s) {
var MOD = 1003;
var m = (s.length + 1) >> 1;
var T = [], F = [];
for (var r = 0; r < m; r++) {
T.push(new Array(m).fill(0));
F.push(new Array(m).fill(0));
}
for (var i = 0; i < m; i++) {
if (s.charAt(2 * i) === "T") T[i][i] = 1; else F[i][i] = 1;
}
for (var len = 2; len <= m; len++) {
for (var a = 0; a + len - 1 < m; a++) {
var b = a + len - 1;
var t = 0, f = 0;
for (var k = a; k < b; k++) {
var lt = T[a][k], lf = F[a][k], rt = T[k + 1][b], rf = F[k + 1][b];
var op = s.charAt(2 * k + 1);
if (op === "&") {
t += lt * rt;
f += lt * rf + lf * rt + lf * rf;
} else if (op === "|") {
t += lt * rt + lt * rf + lf * rt;
f += lf * rf;
} else {
t += lt * rf + lf * rt;
f += lt * rt + lf * rf;
}
t %= MOD;
f %= MOD;
}
T[a][b] = t;
F[a][b] = f;
}
}
return T[0][m - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming