334. Boolean Parenthesization Problem

Given a sequence of n boolean symbols ('T' for true, 'F' for false) separated by n-1 boolean operators (each '&', '|', or '^'), count the number of ways to fully parenthesize the expression such that it evaluates to true.

Input: Two lines: the first contains the symbol string ('T'/'F', length n), the second contains the operator string ('&', '|', '^', length n-1). Output: Print a single integer - the number of parenthesizations that evaluate to true.

1 <= n <= 200

Tracking BOTH T and F counts together (not just T alone) is what makes the recurrence work at all - since a later combination might need to know the FALSE count of an earlier sub-range just as much as its TRUE count, depending on which operator connects them.

Count the ways to parenthesize a boolean expression so it evaluates to true. Brute force: Try every possible way of fully parenthesizing the expression directly and evaluate each - this is exponential (related to the Catalan number of possible parenthesizations), impractical for larger n without memoization. Optimised: Tracking BOTH true-count AND false-count for every sub-range (not just true-count alone) is essential, since combining two sub-ranges via an operator's truth table needs to know how many ways EACH side could be true OR false - building this bottom-up by increasing range length ensures every needed smaller sub-range is already computed.

Fill the same (trueCount, falseCount) table iteratively in order of increasing interval length, so that whenever interval (i, j) is being computed, every smaller sub-interval it depends on has already been finalized. This removes recursion overhead and the risk of deep call stacks for n up to 200, while keeping the same overall complexity as the memoized version. Time: O(n^3) Space: O(n^2)

Apply the exact same recursive split-and-combine logic, but cache the (trueCount, falseCount) pair computed for each interval (i, j) the first time it's needed, so overlapping sub-intervals reached via different split points are solved only once. This bounds the work to the number of distinct intervals rather than the number of ways to split them recursively. Time: O(n^3) Space: O(n^2)

For every interval of the expression, try every operator within it as the 'last' one to be applied, recursively compute how many ways the left part can evaluate to true and to false and the same for the right part, then combine those counts according to that operator's truth table (for example, '&' is true only when both sides are true, '|' is true unless both sides are false, and '^' is true exactly when the two sides differ) and sum over every choice of splitting operator. Without caching, the same sub-intervals get recomputed repeatedly from different split choices, causing exponential blowup. Time: O(4^n) Space: O(n)

1. For a range of symbols i..j, track T[i][j] = number of parenthesizations evaluating to TRUE, and F[i][j] = the number evaluating to FALSE. 2. For every possible SPLIT POINT k between i and j (splitting on operator k), combine the LEFT part's (T,F) counts with the RIGHT part's (T,F) counts according to that operator's truth table. 3. Sum the contribution from every possible split point k, then the final answer is T[0][n-1].

Time: O(n³) - for each of the O(n²) sub-ranges, trying every possible split point costs O(n). Space: O(n²), for the T and F tables.

Test n = 1 (a single symbol, no operators - the count is 1 if it's 'T', else 0) and n = 200 (upper bound) for the O(n^3) interval DP's performance.

Be ready to work through one operator's truth-table combination explicitly (e.g., for '&', true requires BOTH sides true: contributes T[i][k]*T[k+1][j] to T[i][j], and everything else contributes to F[i][j]) - clearly explaining this combination step is the crux of the whole problem.