Boolean Parenthesization

Hard
1606.

Boolean Parenthesization

Boolean Parenthesization is a hard coding problem on strings and dynamic programming, asked in Amazon, Microsoft, Flipkart and Samsung interviews.

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 <= 199
  • s.length is odd
  • s[i] is 'T' or 'F' at even i and one of '&', '|', '^' at odd i
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var countWays = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 199
  • s.length is odd
  • s[i] is 'T' or 'F' at even i and one of '&', '|', '^' at odd i

Hints for Boolean Parenthesization

  1. Hint 1

    Whatever the parenthesisation, one operator is applied last. It splits the expression into a left part and a right part.

  2. 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.

  3. Hint 3

    Let T[i][j] and F[i][j] count the true/false groupings of operands i..j. For a last operator between k and k+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

  1. Let m be the number of operands (operand i is s[2i], the operator after it is s[2i + 1]). Set T[i][i] = 1, F[i][i] = 0 for 'T' and the reverse for 'F'.
  2. For lengths 2..m and every interval i..j, for every split k in i..j-1 with operator op = s[2k + 1] and counts lt, lf for i..k, rt, rf for k+1..j:
  3. &: 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.
  4. 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 ^ T and T ^ F need the false counts of a part.
  • Operands and operators interleave — operand i is at index 2i, not i.
  • 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