Boolean Parenthesization Problem

The problem, simply

You get a string like T|T&F^T. The letters are T (true) and F (false). Between every two letters is an operator:

• & (and) is true only when both sides are true.
• | (or) is true when at least one side is true.
• ^ (xor) is true when the two sides are different.

You may put brackets anywhere, which changes the order the operators are done in. Count how many different bracketings make the whole thing true. The count grows fast, so the judge usually wants it modulo 1003.

A story to remember it

Picture it

Examples

Way 1: the simple way

Pick the operator that is done last. Everything to its left becomes one value and everything to its right becomes another. Ask the same question about each side, for both true and false, and combine.

1. A single letter: T is true in 1 way, F is false in 1 way.
2. For a longer piece, try every operator as the last cut.
3. Get (leftTrue, leftFalse) and (rightTrue, rightFalse) by asking the smaller pieces.
4. Add up the ways the operator gives true. All other pairs give false.

We must count false ways too: ^ is true when one side is false, and | is true even if one side is false.

class Solution {
    // returns {ways to be true, ways to be false} for s[i..j]
    // i and j are positions of letters, operators sit at odd positions
    int[] count(String s, int i, int j) {
        if (i == j) return s.charAt(i) == 'T' ? new int[]{1, 0} : new int[]{0, 1};
        int t = 0, f = 0;
        for (int k = i + 1; k < j; k += 2) {        // k is an operator
            int[] L = count(s, i, k - 1);
            int[] R = count(s, k + 1, j);
            int all = (L[0] + L[1]) * (R[0] + R[1]);
            char op = s.charAt(k);
            int tr;
            if (op == '&') tr = L[0] * R[0];
            else if (op == '|') tr = L[0] * R[0] + L[0] * R[1] + L[1] * R[0];
            else tr = L[0] * R[1] + L[1] * R[0];          // '^'
            t += tr;
            f += all - tr;
        }
        return new int[]{t, f};
    }

    public int countWays(int n, String s) {
        return count(s, 0, n - 1)[0];
    }
}

How long it takes: a piece of m letters calls every shorter piece on each side, and the work about triples with each extra letter, O(3^n) for n letters. Extra room: the chain of waiting calls, O(n).

Way 2: the clever way

There are only about n * n / 2 different pieces (a start letter and an end letter). Keep two tables, T[i][j] and F[i][j]: the ways letters i..j come out true and false. Fill short pieces first, because a long piece only uses shorter ones.

1. Fill the diagonal: one letter each.
2. For length 2, 3, ... up to all letters, for every start i (end j = i + len - 1):
3. Try every cut k between i and j. Combine T[i][k], F[i][k] with T[k+1][j], F[k+1][j] using the operator after letter k.
4. The answer is T[0][n-1].

class Solution {
    static final int MOD = 1003;   // the judge asks for the answer modulo 1003

    public int countWays(int n, String s) {
        int m = (n + 1) / 2;                       // number of T and F letters
        int[][] T = new int[m][m];                 // T[i][j]: ways letters i..j are true
        int[][] F = new int[m][m];                 // F[i][j]: ways letters i..j are false
        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 i = 0; i + len - 1 < m; i++) {
                int j = i + len - 1;
                for (int k = i; k < j; k++) {      // cut after letter k
                    char op = s.charAt(2 * k + 1);
                    int lt = T[i][k], lf = F[i][k], rt = T[k + 1][j], rf = F[k + 1][j];
                    int all = (lt + lf) * (rt + rf) % MOD;
                    int tr;
                    if (op == '&') tr = lt * rt % MOD;
                    else if (op == '|') tr = (lt * rt + lt * rf + lf * rt) % MOD;
                    else tr = (lt * rf + lf * rt) % MOD;
                    T[i][j] = (T[i][j] + tr) % MOD;
                    F[i][j] = (F[i][j] + all - tr + MOD) % MOD;
                }
            }
        }
        return T[0][m - 1];
    }
}

How long it takes: about n^2 / 2 boxes, and each tries up to n cuts, O(n^3). Extra room: two tables, O(n^2).

Watch out for

• Letters and operators share one string. Letter i is at 2 * i, and the operator after it is at 2 * i + 1.
• With a modulo, all - tr can be negative. Add MOD before taking % again.
• Fill by length, not row by row from the top. T[i][j] needs T[k + 1][j], which sits lower in the table.

What interviewers ask next

• Count the ways to get false instead. Return F[0][n-1]. The table already has it.
• What if every operator were the same? The number of bracketings of n letters is the Catalan number C(n-1), so the answer is a part of that.
• "Different ways to add parentheses" with numbers and + - * asks for every result value. Same cut-at-the-last-operator idea, but each piece keeps a list of values instead of two counts.
• How does this relate to matrix chain multiplication? Same shape: try every last split of a range, short ranges first. That family is called interval DP.

Remember this

Grown-up words: a piece of the expression is an interval, the tables T and F are the DP states, filling by length is interval DP, the last operator is the split point, and drawing an expression as a tree gives an expression tree.