Solving Boolean Parenthesization with Dynamic Programming

1. Introduction and Core Concepts

Boolean parenthesization is a classic dynamic programming problem that asks a deceptively simple question: given a boolean expression consisting of symbols and operators, in how many different ways can we parenthesize the expression so that it evaluates to true? The expression is typically provided as a sequence of operands, each being either T (true) or F (false), interleaved with binary boolean operators such as AND (&), OR (|), and XOR (^). For example, the expression T | F & T ^ F can be parenthesized in five distinct ways, but only a subset of those parenthesizations will evaluate to true.

At its heart, the problem is a counting problem over the space of binary trees. For an expression with n symbols, there are n-1 operators, and the number of ways to fully parenthesize it is given by the Catalan number C(n-1) = (2n-2)! / ((n-1)! * n!). This number grows exponentially, approximately as 4^n / (n^(3/2) * sqrt(pi)). For even modest values of n, exhaustive enumeration becomes computationally infeasible, which is precisely why a systematic dynamic programming approach is required. The problem is not just about finding one valid parenthesization, but counting all of them efficiently.

Understanding boolean parenthesization matters far beyond coding interviews. It exemplifies the core principles of interval dynamic programming, a paradigm also used for matrix chain multiplication, optimal binary search trees, and polygon triangulation. It teaches how to decompose a problem into overlapping subproblems defined over intervals, how to combine results using operator-specific truth tables, and how to handle two interdependent DP states simultaneously. Mastering this problem provides a template for solving a whole family of partition-based DP problems where the optimal or total solution depends on every possible split point.

Why Counting Parenthesizations Is Non-Trivial

A naive approach might attempt to generate all parenthesizations recursively and evaluate each one. While correct, this approach recomputes the same subexpressions many times. For instance, in the expression T | F & T ^ F | T, the subexpression F & T will be evaluated in multiple different larger contexts. Dynamic programming eliminates this redundancy by storing the number of ways each subexpression can evaluate to true and to false, allowing us to answer the larger problem in polynomial time.

Another subtlety is that we must track both true and false counts for every interval. Unlike optimization problems where we store a single best value, counting problems with boolean operators require both outcomes. This is because the truth value of a parent expression depends on the combination of truth values of its left and right children. For example, A & B is true only when both A and B are true, but A | B is true when either is true. Without knowing how many ways a subexpression can be false, we cannot correctly compute how many ways the parent can be true.

2. How It Works

The dynamic programming solution for boolean parenthesization is built on interval DP. We define two two-dimensional tables, T[i][j] and F[i][j], where 0 <= i <= j < n. T[i][j] stores the number of ways to parenthesize the subexpression from symbol i to symbol j inclusive such that it evaluates to true. Similarly, F[i][j] stores the number of ways it evaluates to false. The total number of ways to parenthesize the interval [i, j] is T[i][j] + F[i][j], which should equal the Catalan number for that interval length if counting is correct.

The base case is straightforward: for a single symbol interval where i == j, there is only one way to parenthesize (no parentheses needed). If the symbol is T, then T[i][i] = 1 and F[i][i] = 0. If the symbol is F, then T[i][i] = 0 and F[i][i] = 1. This initialization anchors the entire DP table and ensures that larger intervals can be built compositionally from smaller ones.

For larger intervals where i < j, we consider every possible position to place the last (outermost) parenthesis. This corresponds to choosing a split point k where i <= k < j, meaning the operator at index k (between symbols k and k+1) is the final operator to be evaluated. The left subexpression is [i, k] and the right subexpression is [k+1, j]. For each split, we combine the counts from the left and right using the truth table of the operator at k. The total for T[i][j] and F[i][j] is the sum over all possible splits.

Operator-Specific Recurrence Relations

The combination logic depends entirely on the operator. Let leftTrue = T[i][k], leftFalse = F[i][k], rightTrue = T[k+1][j], and rightFalse = F[k+1][j]. The total combinations for this split is (leftTrue + leftFalse) * (rightTrue + rightFalse). How this total is partitioned into true and false outcomes is operator-specific:

• AND (&): True only when both sides are true. So trueWays = leftTrue * rightTrue and falseWays = leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse.
• OR (|): False only when both sides are false. So trueWays = leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue and falseWays = leftFalse * rightFalse.
• XOR (^): True when sides differ. So trueWays = leftTrue * rightFalse + leftFalse * rightTrue and falseWays = leftTrue * rightTrue + leftFalse * rightFalse.

By iterating over all split points k and accumulating these contributions, we fill the tables diagonally, increasing interval length from 1 to n. The final answer is T[0][n-1]. This bottom-up order guarantees that when we compute T[i][j], all required smaller intervals [i, k] and [k+1, j] have already been computed.

3. Implementation

Implementing boolean parenthesization can be done using either top-down memoization or bottom-up tabulation. Both achieve the same asymptotic complexity, but they differ in implementation style, constant factors, and ease of understanding. Below are four distinct Python implementations that illustrate the progression from exponential brute force to efficient dynamic programming.

The first implementation shows the naive recursive solution without memoization. It directly mirrors the mathematical recurrence and is useful for understanding the problem structure, but it has exponential time complexity and will time out for n > 15 due to repeated subproblem computation.

def count_bruteforce(symbols, operators, i, j, is_true):
    """
    Brute-force recursive count without memoization.
    symbols: list of 'T'/'F', operators: list of '&','|','^'
    i, j: interval indices inclusive, is_true: target boolean value
    """
    # Base case: single symbol
    if i == j:
        if is_true:
            return 1 if symbols[i] == 'T' else 0
        else:
            return 1 if symbols[i] == 'F' else 0

    ans = 0
    # Try every operator k as the last split point
    for k in range(i, j):
        op = operators[k]
        # Recursively count left and right possibilities
        left_true = count_bruteforce(symbols, operators, i, k, True)
        left_false = count_bruteforce(symbols, operators, i, k, False)
        right_true = count_bruteforce(symbols, operators, k+1, j, True)
        right_false = count_bruteforce(symbols, operators, k+1, j, False)

        total_left = left_true + left_false
        total_right = right_true + right_false

        if op == '&':
            if is_true:
                ans += left_true * right_true
            else:
                ans += left_true * right_false + left_false * right_true + left_false * right_false
        elif op == '|':
            if is_true:
                ans += left_true * right_true + left_true * right_false + left_false * right_true
            else:
                ans += left_false * right_false
        elif op == '^':
            if is_true:
                ans += left_true * right_false + left_false * right_true
            else:
                ans += left_true * right_true + left_false * right_false
    return ans

# Example: T | F & T
# symbols = ['T','F','T']; operators = ['|','&']
# print(count_bruteforce(symbols, operators, 0, 2, True))  # Output: 2

The second implementation adds memoization to the recursive approach. This top-down DP stores results of previously computed states in a dictionary, reducing the time complexity from exponential to polynomial. It is often easier to write correctly in an interview because it preserves the natural recursive structure while gaining efficiency.

def count_memoized(symbols, operators):
    n = len(symbols)
    memo = {}

    def dp(i, j, is_true):
        # Check memo table
        if (i, j, is_true) in memo:
            return memo[(i, j, is_true)]

        # Base case
        if i == j:
            if is_true:
                res = 1 if symbols[i] == 'T' else 0
            else:
                res = 1 if symbols[i] == 'F' else 0
            memo[(i, j, is_true)] = res
            return res

        ans = 0
        for k in range(i, j):
            op = operators[k]
            lt = dp(i, k, True)
            lf = dp(i, k, False)
            rt = dp(k+1, j, True)
            rf = dp(k+1, j, False)

            if op == '&':
                if is_true:
                    ans += lt * rt
                else:
                    ans += lt * rf + lf * rt + lf * rf
            elif op == '|':
                if is_true:
                    ans += lt * rt + lt * rf + lf * rt
                else:
                    ans += lf * rf
            elif op == '^':
                if is_true:
                    ans += lt * rf + lf * rt
                else:
                    ans += lt * rt + lf * rf

        memo[(i, j, is_true)] = ans
        return ans

    return dp(0, n-1, True)

# Handles larger inputs efficiently
# symbols = ['T','F','T','F']; operators = ['|','&','^']
# print(count_memoized(symbols, operators))

The third implementation is the classic bottom-up tabulation. It iteratively fills two n x n tables, T and F, by increasing gap length. This approach avoids recursion overhead, eliminates the risk of stack overflow, and is typically the most cache-efficient and fastest in practice. It is the preferred solution for production code and competitive programming.

def count_tabulation(symbols, operators):
    """
    Bottom-up DP with O(n^3) time and O(n^2) space.
    Returns number of ways to parenthesize to True.
    """
    n = len(symbols)
    # T[i][j] = ways to get True for interval i..j
    # F[i][j] = ways to get False for interval i..j
    T = [[0]*n for _ in range(n)]
    F = [[0]*n for _ in range(n)]

    # Base case: single symbols
    for i in range(n):
        if symbols[i] == 'T':
            T[i][i] = 1
            F[i][i] = 0
        else:
            T[i][i] = 0
            F[i][i] = 1

    # Fill by gap length
    for gap in range(1, n):
        for i in range(n - gap):
            j = i + gap
            T[i][j] = 0
            F[i][j] = 0
            for k in range(i, j):
                op = operators[k]
                # All combinations for split at k
                # left = i..k, right = k+1..j
                tik = T[i][k] + F[i][k]
                tk1j = T[k+1][j] + F[k+1][j]

                if op == '&':
                    T[i][j] += T[i][k] * T[k+1][j]
                    F[i][j] += (T[i][k] * F[k+1][j] + 
                                F[i][k] * T[k+1][j] + 
                                F[i][k] * F[k+1][j])
                elif op == '|':
                    F[i][j] += F[i][k] * F[k+1][j]
                    T[i][j] += (T[i][k] * T[k+1][j] + 
                                T[i][k] * F[k+1][j] + 
                                F[i][k] * T[k+1][j])
                elif op == '^':
                    T[i][j] += T[i][k] * F[k+1][j] + F[i][k] * T[k+1][j]
                    F[i][j] += T[i][k] * T[k+1][j] + F[i][k] * F[k+1][j]

    return T[0][n-1]

# Example usage
# expr_symbols = ['T','T','F','T']
# expr_ops = ['|','&','^']
# print(count_tabulation(expr_symbols, expr_ops))

The fourth implementation extends the tabulation approach to handle modulo arithmetic and input parsing from a string expression, which is how the problem is often presented in online judges. It also demonstrates how to handle large counts that would otherwise overflow 32-bit integers.

MOD = 1003  # Common modulus for interview problems

def count_from_string(expression, mod=MOD):
    """
    Parses string like "T|F&T^F" and counts ways to get True modulo mod.
    Handles large n with modulo to prevent overflow.
    """
    symbols = []
    operators = []
    for ch in expression:
        if ch == 'T' or ch == 'F':
            symbols.append(ch)
        elif ch in ('&', '|', '^'):
            operators.append(ch)

    n = len(symbols)
    if n == 0:
        return 0

    T = [[0]*n for _ in range(n)]
    F = [[0]*n for _ in range(n)]

    for i in range(n):
        T[i][i] = 1 if symbols[i] == 'T' else 0
        F[i][i] = 1 if symbols[i] == 'F' else 0

    for gap in range(1, n):
        for i in range(n - gap):
            j = i + gap
            for k in range(i, j):
                op = operators[k]
                # Use modulo for large counts
                if op == '&':
                    T[i][j] = (T[i][j] + T[i][k] * T[k+1][j]) % mod
                    F[i][j] = (F[i][j] + T[i][k] * F[k+1][j] + 
                               F[i][k] * T[k+1][j] + 
                               F[i][k] * F[k+1][j]) % mod
                elif op == '|':
                    F[i][j] = (F[i][j] + F[i][k] * F[k+1][j]) % mod
                    T[i][j] = (T[i][j] + T[i][k] * T[k+1][j] + 
                               T[i][k] * F[k+1][j] + 
                               F[i][k] * T[k+1][j]) % mod
                elif op == '^':
                    T[i][j] = (T[i][j] + T[i][k] * F[k+1][j] + 
                               F[i][k] * T[k+1][j]) % mod
                    F[i][j] = (F[i][j] + T[i][k] * T[k+1][j] + 
                               F[i][k] * F[k+1][j]) % mod
    return T[0][n-1] % mod

# print(count_from_string("T|T&F^T", mod=1003))
# print(count_from_string("T^F|F", mod=1000000007))

4. Step-by-Step Example

Let us walk through a concrete example to solidify the mechanics. Consider the expression T ^ F | F. Here, symbols = ['T', 'F', 'F'] and operators = ['^', '|'] with n = 3. There are two operators, so there are C(2) = 2 ways to parenthesize: (T ^ F) | F and T ^ (F | F). Evaluating them: (T ^ F) = T, then T | F = T (true). (F | F) = F, then T ^ F = T (true). Both evaluate to true, so the answer should be 2. Let us see how DP arrives at this result.

We initialize the base tables for intervals of length 1. For i = 0 (T): T[0][0]=1, F[0][0]=0. For i = 1 (F): T[1][1]=0, F[1][1]=1. For i = 2 (F): T[2][2]=0, F[2][2]=1. These are the leaves of our computation.

Next, we compute intervals of length 2 (gap = 1). For interval [0,1] with operator ^ at k=0: left = [0,0] (T), right = [1,1] (F). For XOR, true ways are T_left * F_right + F_left * T_right = 1*1 + 0*0 = 1. False ways are T_left * T_right + F_left * F_right = 1*0 + 0*1 = 0. So T[0][1]=1, F[0][1]=0. For interval [1,2] with operator | at k=1: left = F, right = F. For OR, false ways are F_left * F_right = 1*1 = 1, true ways are 0. So T[1][2]=0, F[1][2]=1.

Finally, we compute the full interval [0,2] (gap = 2). We must consider both split points. Split at k=0 (operator ^): left is [0,0] (T:1, F:0), right is [1,2] (T:0, F:1). For XOR: true = 1*1 + 0*0 = 1, false = 1*0 + 0*1 = 0. Split at k=1 (operator |): left is [0,1] (T:1, F:0), right is [2,2] (T:0, F:1). For OR: true = 1*0 + 1*1 + 0*0 = 1, false = 0*1 = 0. Summing contributions from both splits: T[0][2] = 1 (from k=0) + 1 (from k=1) = 2, F[0][2] = 0 + 0 = 0. The final answer T[0][2]=2 matches our manual enumeration.

Visualizing the DP Table Fill Order

The table is filled along diagonals. First the main diagonal (gap 0), then the first super-diagonal (gap 1), and so on until the top-right cell. This ensures that any interval [i, j] only depends on strictly smaller intervals that have already been computed. If we attempted to fill row by row, we would encounter dependencies on not-yet-computed cells.

This example also highlights why tracking both true and false counts is essential. When computing [0,2] with split at k=0, we needed F[1][2] to compute the true ways for XOR, even though [1,2] itself has zero true ways. A table that only stored true counts would be insufficient to propagate the logic correctly for operators like XOR and OR.

5. Complexity Analysis

The complexity of boolean parenthesization is well-understood and serves as a textbook example of trading exponential time for polynomial time via dynamic programming. The naive recursive solution explores the full Catalan space, leading to exponential blowup, while the DP variants achieve cubic time by reusing subproblem results.

For an expression with n symbols, there are O(n^2) distinct intervals [i, j]. For each interval, we iterate over O(n) possible split points k. At each split, we perform O(1) arithmetic operations to combine the four values T[i][k], F[i][k], T[k+1][j], F[k+1][j]. This yields a total time complexity of O(n^3) for both memoized and tabulated DP. The space complexity is dominated by the two n x n tables, giving O(n^2) space. The recursion stack for the memoized version adds an additional O(n) overhead in the worst case, but this does not change the asymptotic bound.

It is important to note that the O(n^3) bound is tight and applies to best, average, and worst cases for the DP algorithms. Unlike sorting or searching algorithms where input distribution affects performance, the DP must fill the entire table regardless of the specific arrangement of T, F, and operators. The only variation is in the constant factors due to different operator mixes, but the number of operations remains cubic.

*Note: Unlike matrix chain multiplication or optimal BST, boolean parenthesization does not satisfy the quadrangle inequality or monotonicity property required for Knuth or Hu-Shing optimization. Therefore, no general O(n^2) optimization exists for arbitrary operators; the table entry remains O(n^3) as the optimal bound.

When modulo arithmetic is required (common in competitive programming to avoid integer overflow), the time complexity remains O(n^3) with a slightly higher constant factor due to modulo operations. For very large n (e.g., n > 500), even O(n^3) may be too slow, and the problem constraints typically limit n to 100-200 for the cubic solution to pass. The space can be optimized to O(n^2) is already optimal; attempts to reduce to O(n) fail because intervals of all lengths are needed for future computations.

6. Variations and Optimizations

The classic boolean parenthesization problem admits several interesting variations that appear in advanced interviews and research. One common variant asks not just for the count of ways to get true, but for both true and false counts, or for the count modulo a large prime like 10^9+7. Another variant introduces additional operators such as NAND, NOR, or implication, which require extending the truth table logic but do not change the DP structure. Some problems also allow parentheses to be placed arbitrarily, not just in binary splits, though this is equivalent to the binary tree formulation.

A more challenging variation is to count parenthesizations that evaluate to true with a minimum or maximum number of operator evaluations, or to find the parenthesization that maximizes the probability of being true when symbols are probabilistic (e.g., T with probability p). This transforms the counting problem into an optimization problem and requires storing not just counts but also best values. Another extension is to handle expressions with variables and to count assignments of variables that make the expression true for at least one parenthesization, blending boolean satisfiability with parenthesization.

Optimization techniques for the standard problem are limited but worth discussing. Since the DP is already optimal at O(n^3), micro-optimizations focus on reducing constant factors. One technique is to use iterative loops with local variable caching to avoid repeated table lookups. Another is to use NumPy or PyPy for faster array operations in Python, though the triple nested loop remains the bottleneck. For languages like C++ or Java, bitset optimizations are not applicable here, but using short integers and early pruning for zero intervals can help.

Handling Large Inputs and Modulo

In practice, the number of ways can be astronomically large. For n=100, the Catalan number is around 10^56, far exceeding 64-bit integer limits. Therefore, most problem statements require the answer modulo M (e.g., 1003, 10^9+7). When applying modulo, care must be taken to apply it after each addition and multiplication to prevent intermediate overflow in Python (though Python handles big integers, modulo keeps numbers small and fast) and especially in lower-level languages.

Another optimization is to use memoization with lru_cache in Python for cleaner code. The functools.lru_cache decorator can automatically handle memoization for the recursive solution, reducing boilerplate and making the code more readable while maintaining O(n^3) performance.

7. Real-World Applications

While boolean parenthesization may seem like an abstract combinatorial puzzle, its underlying principles appear in numerous real-world systems where expression evaluation, query optimization, and probabilistic reasoning are critical. The core idea of counting or optimizing over all binary tree structures for an associative operation is widely applicable.

In database systems, query optimizers must decide the order in which to join tables or apply filter predicates. A query like (A AND B) OR (C AND D) can be executed in multiple orders, and the optimizer estimates the cost and selectivity (probability of being true) of each parenthesization. Counting the number of equivalent execution plans is analogous to counting parenthesizations, and dynamic programming is used to find the cheapest plan, similar to how boolean parenthesization counts true evaluations. The same interval DP structure is used for join order optimization.

In compiler design and circuit synthesis, boolean expressions are represented as expression trees. Different parenthesizations correspond to different circuit depths and gate arrangements. Counting the number of ways to achieve a true output helps in logic minimization, test vector generation, and fault analysis. For example, in designing an arithmetic logic unit (ALU), engineers may want to know how many input assignments make a particular output true under different tree structures to optimize for power or delay.

In network reliability and probabilistic reasoning, boolean parenthesization models the reliability of series-parallel networks where components can be connected via AND (series, both must work) and OR (parallel, at least one must work). The count of true evaluations corresponds to the number of operational states, which can be converted to reliability probabilities. Similarly, in artificial intelligence, parsing ambiguous grammars where a sentence can have multiple parse trees that evaluate to true or false uses the same counting mechanism.

Even in web servers and load balancers, boolean conditions for routing rules (e.g., (path == "/api" AND method == "GET") OR (header == "mobile")) can be parenthesized differently for evaluation efficiency. While not counting parenthesizations directly, the optimizer that reorders conditions to minimize average evaluation time uses similar DP principles to find the best parenthesization for short-circuit evaluation.

8. Comparison with Alternatives

Boolean parenthesization is one member of a larger family of interval DP problems. Understanding how it compares to related approaches helps in selecting the right technique for a given problem and in recognizing the problem pattern during interviews. The key differentiator is whether the problem requires counting, optimization, or decision, and whether the combine step depends on both true and false subcounts.

Brute-force recursion is the baseline alternative. It is simple to implement and requires no extra space, but it is only feasible for very small n (typically n <= 12). It serves as a correctness reference for testing DP implementations on small inputs but is never suitable for production or interview constraints where n can be up to 100 or more.

Divide and conquer without memoization is essentially the same as brute force in this context, as the subproblems overlap heavily. Memoization transforms it into top-down DP, which has the same complexity as bottom-up but differs in implementation trade-offs: top-down is more intuitive and only computes needed states (though in this problem all states are needed), while bottom-up has better constant factors and avoids recursion limits.

Greedy approaches are not applicable to boolean parenthesization. A greedy strategy that always splits at the operator that locally maximizes true ways will fail to find the global count, as the optimal split depends on the combination of left and right counts, not just a local choice. This contrasts with some optimization problems where greedy can work, but for counting, every split must be considered.

Matrix chain multiplication is the closest analogue. Both use interval DP with O(n^3) time and O(n^2) space, both iterate over split points k, and both fill tables diagonally. The difference is that matrix chain stores a single minimum cost, while boolean parenthesization stores two counts that interact via truth tables. Recognizing this pattern allows you to transfer intuition between problems: if you can solve one, you can solve the other with minor modifications to the recurrence.

9. Common Mistakes and Best Practices

Even experienced programmers make subtle errors when implementing boolean parenthesization. The most frequent mistake is tracking only true counts and ignoring false counts. As emphasized earlier, operators like XOR and OR require false counts to compute true counts correctly. For example, T[i][j] for OR depends on F[i][k] * F[k+1][j] for the false case, and without F, the true count will be undercounted. Always maintain both tables or a combined structure that stores both values.

Another common pitfall is incorrect indexing of operators. Symbols are indexed 0..n-1, while operators are indexed 0..n-2, where operator k is between symbols k and k+1. When splitting interval [i, j] at k, the operator is operators[k], the left interval is [i, k], and the right is [k+1, j]. Off-by-one errors here lead to using the wrong operator for a split or accessing out-of-bounds indices. Carefully drawing the relationship between symbol and operator indices during implementation prevents this.

Integer overflow and modulo handling are also frequent sources of bugs. In languages with fixed-size integers, the counts can overflow quickly, so modulo must be applied consistently after every multiplication and addition. In Python, big integers hide the overflow but can cause performance degradation for large n if modulo is not used. Also, be careful to apply modulo to both T and F tables, not just the final answer, as intermediate values are used in subsequent computations.

Best Practices for Robust Implementation

To avoid these pitfalls, follow a set of best practices. First, write a helper function to parse the input expression into separate symbol and operator lists, and validate that len(symbols) == len(operators) + 1. This catches malformed inputs early. Second, initialize the DP tables with the correct base cases and use a clear loop structure: outer loop over gap length, middle loop over start index i, inner loop over split k. This diagonal fill order is less error-prone than trying to fill row by row.

Third, write a small brute-force verifier for n <= 8 and test your DP against it on random expressions. This differential testing quickly catches logic errors in the operator truth tables. Fourth, use descriptive variable names like leftTrue and rightFalse instead of a, b, c, d to make the truth table logic self-documenting. Finally, if the problem requires modulo, define MOD as a constant and create a helper function for modular addition and multiplication to ensure consistency.

Lastly, consider edge cases: n=1 (single symbol, no operators), all symbols are T or all F, and expressions with only one type of operator. Testing these cases ensures your base case and recurrence handle extremes correctly. For n=1, the answer should be 1 if the symbol is T and we count true ways, otherwise 0.

10. Interview Questions

Boolean parenthesization is a favorite in technical interviews for senior and advanced roles because it tests multiple skills simultaneously: dynamic programming, careful case analysis, and handling of combinatorial counting. Interviewers often use variations to probe depth of understanding beyond the standard problem.

Question 1: Count the number of ways to parenthesize the expression to get false instead of true. This is a straightforward extension. The DP already computes F[0][n-1], so the answer is simply the false table's top-right cell. The interviewer wants to see if you understand that both tables are needed and that the solution is symmetric. A follow-up might ask to return both counts as a pair, testing whether you can adapt the return value without recomputing.

Question 2: How would you modify the solution if the operators include NAND and NOR, or if the expression contains variables that can be assigned T/F? For NAND (!(A & B)) and NOR (!(A | B)), you need to invert the truth tables: NAND is false only when both are true, so trueWays = total - leftTrue*rightTrue. For variables, the problem becomes counting assignments plus parenthesizations, which requires an additional dimension in the DP or a separate SAT-like counting step. This tests ability to extend the recurrence to new operators.

Question 3: Can you reconstruct one parenthesization that evaluates to true, or list all such parenthesizations? Counting is one thing, reconstruction is another. To reconstruct one valid parenthesization, you can backtrack through the DP tables: starting from [0, n-1] with target true, find a split k where the operator and subcounts allow a true outcome, then recursively reconstruct left and right. To list all, you would need to generate all trees, which is exponential in output size, but you can discuss the approach. This tests understanding of DP backtracking.

Question 4: What is the time and space complexity, and can you optimize it to O(n^2) or O(n) space? The expected answer is O(n^3) time and O(n^2) space, with the explanation that O(n^3) is optimal due to the need to consider all splits and that space cannot be reduced to O(n) because all intervals are needed. Some candidates mistakenly claim O(n^2) time via Knuth optimization, but as noted, the quadrangle inequality does not hold for boolean operators, so such optimization is invalid. This tests rigorous complexity analysis.

Question 5: How would you handle an expression with 10^5 symbols? Is DP still feasible? For n=10^5, O(n^3) is impossible. The interviewer is probing awareness of constraints and alternative approaches. You should discuss that for such large n, the problem as stated is intractable, and you would need to consider approximation, sampling, or exploiting structure (e.g., if operators are all the same, closed-form formulas may exist). For all ANDs, the expression is true only if all symbols are true, so count is 1 if all T else 0, independent of parenthesization. Recognizing such special cases shows practical problem-solving maturity.