DEV Community

Cover image for Boolean Parenthesization: The MCM Skeleton, Counting Instead of Minimising
Nishant Gaurav
Nishant Gaurav

Posted on

Boolean Parenthesization: The MCM Skeleton, Counting Instead of Minimising

#ai #programming #python #discuss

Boolean Parenthesization: The MCM Skeleton, Counting Instead of Minimising

Matrix Chain Multiplication had matrices and multiplication costs. Palindrome Partitioning swapped that for a string and a +1 per cut. Boolean Parenthesization keeps the same skeleton again, but this time the combining step gets genuinely more involved, because the answer isn't a single number anymore, it's two: how many ways to reach True, and how many ways to reach False.

The Problem

Given a Boolean expression made of T, F, and the operators &, |, ^, count how many distinct ways you can parenthesize it so the whole thing evaluates to True.

s = T | F & T

Two valid parenthesizations:
  (T | F) & T   → evaluates to True
  T | (F & T)   → evaluates to True

Answer: 2
Enter fullscreen mode Exit fullscreen mode

This isn't asking whether a True evaluation exists. It's asking how many structurally different ways of grouping the expression land on True.

Recognising the MCM Pattern

The same four signals from the MCM chapter show up here. There's a sequence you can partition (the expression). A minimum, or in this case a count, is being asked for. Multiple partition points are possible, one for each operator in the string.

Expression:       T | F & T
Partitions:       T | (F & T)
                   (T | F) & T
Counting answer:  yes
Multiple k:       yes
Enter fullscreen mode Exit fullscreen mode

The same (i, j, k) structure applies, with i and j marking the boundaries of the current substring and k marking where you split it. The difference shows up almost immediately once you try to define what solve(i, j) should even return.

Why One Number Isn't Enough

In MCM, solve(i, j) returns a single number, the minimum cost. In Palindrome Partitioning, solve(i, j) also returns a single number, the minimum cuts. Here, a single number breaks down almost immediately once you think through what combining two sides actually requires.

Take the XOR operator. Left ^ Right evaluates to True in exactly two situations: Left is True and Right is False, or Left is False and Right is True.

True ^ False = True
False ^ True = True
Enter fullscreen mode Exit fullscreen mode

To count the ways Left ^ Right can be True, you need to know how many ways Left can be True, how many ways Left can be False, how many ways Right can be True, and how many ways Right can be False, all four, not just one of them. A solve(i, j) that only tracks "minimum cost" or "cuts" has nowhere to put that information.

So the state grows by one dimension. Instead of solve(i, j), it's solve(i, j, isTrue):

solve(s, i, j, isTrue)

isTrue = True  → count of ways s[i..j] evaluates to True
isTrue = False → count of ways s[i..j] evaluates to False
Enter fullscreen mode Exit fullscreen mode

Every call to solve for a given (i, j) range actually needs both variants computed, because the combining step for whichever operator sits at the split point needs both the True count and the False count from each side.

The Base Cases

Two conditions end the recursion, and they mirror the MCM and Palindrome Partitioning base cases closely, just adjusted for the extra isTrue flag.

i > j: An invalid, empty range. Nothing to evaluate. Return 0.

i == j: A single operand remains, either T or F. Whether this counts toward the answer depends on what isTrue is asking for.

if i > j:
    return 0

if i == j:
    if isTrue:
        return 1 if s[i] == 'T' else 0
    else:
        return 1 if s[i] == 'F' else 0
Enter fullscreen mode Exit fullscreen mode

If isTrue is True and the single character is literally T, there's exactly one way to make this range True, itself. If the character is F instead, there are zero ways to make it True. The isTrue = False branch mirrors this exactly, checking for F instead.

Finding k, Operators Only

Just like MCM splits between matrices and Palindrome Partitioning splits between characters, Boolean Parenthesization splits at operator positions. Operands and operators alternate in the string, so k has to land specifically on an operator index, never on a T or F.

Index:  0   1   2   3   4
Value:  T   |   F   &   T
Enter fullscreen mode Exit fullscreen mode

The operators sit at odd indices, 1 and 3. Stepping by 2 starting from i + 1 walks across exactly those positions:

for k in range(i + 1, j, 2):
Enter fullscreen mode Exit fullscreen mode

Each k splits the expression into a left substring s[i..k-1], the operator s[k], and a right substring s[k+1..j].

The Combining Step

This is where the extra dimension actually pays off. For each k, both sides get solved for both True and False:

leftTrue  = solve(s, i, k - 1, True)
leftFalse = solve(s, i, k - 1, False)

rightTrue  = solve(s, k + 1, j, True)
rightFalse = solve(s, k + 1, j, False)
Enter fullscreen mode Exit fullscreen mode

Compare this against the single tempAns line from Palindrome Partitioning:

MCM:                    tempAns = left + right + arr[i-1]*arr[k]*arr[j]
Palindrome Partitioning: tempAns = left + right + 1
Boolean Parenthesization: four separate values, combined differently per operator
Enter fullscreen mode Exit fullscreen mode

There's no single tempAns line here, because the combination depends entirely on which operator sits at k. Each operator has its own truth table, and each truth table tells you exactly which pairs of left and right outcomes multiply together to contribute toward True, and which contribute toward False.

AND (&): True only when both sides are True.

target True:  leftTrue * rightTrue
target False: everything else = (leftTrue * rightFalse) + (leftFalse * rightTrue) + (leftFalse * rightFalse)
Enter fullscreen mode Exit fullscreen mode

OR (|): False only when both sides are False.

target True:  everything else = (leftTrue * rightTrue) + (leftTrue * rightFalse) + (leftFalse * rightTrue)
target False: leftFalse * rightFalse
Enter fullscreen mode Exit fullscreen mode

XOR (^): True only when the sides disagree.

target True:  (leftTrue * rightFalse) + (leftFalse * rightTrue)
target False: (leftTrue * rightTrue) + (leftFalse * rightFalse)
Enter fullscreen mode Exit fullscreen mode

In every case, multiplication combines two independent counts (this is the counting principle: if there are a ways to make the left side a certain value and b ways to make the right side a certain value, there are a * b ways to combine them into that pair), and addition combines multiple mutually exclusive ways of reaching the same target across different operand combinations.

The Recursive Solution 

class Solution:

    def solve(self, s, i, j, isTrue):

        if i > j:
            return 0

        if i == j:
            if isTrue:
                return 1 if s[i] == 'T' else 0
            else:
                return 1 if s[i] == 'F' else 0

        ans = 0

        for k in range(i + 1, j, 2):

            leftTrue = self.solve(s, i, k - 1, True)
            leftFalse = self.solve(s, i, k - 1, False)

            rightTrue = self.solve(s, k + 1, j, True)
            rightFalse = self.solve(s, k + 1, j, False)

            op = s[k]

            if op == '&':
                if isTrue:
                    ans += leftTrue * rightTrue
                else:
                    ans += (
                        leftTrue * rightFalse
                        + leftFalse * rightTrue
                        + leftFalse * rightFalse
                    )

            elif op == '|':
                if isTrue:
                    ans += (
                        leftTrue * rightTrue
                        + leftTrue * rightFalse
                        + leftFalse * rightTrue
                    )
                else:
                    ans += leftFalse * rightFalse

            elif op == '^':
                if isTrue:
                    ans += (
                        leftTrue * rightFalse
                        + leftFalse * rightTrue
                    )
                else:
                    ans += (
                        leftTrue * rightTrue
                        + leftFalse * rightFalse
                    )

        return ans

    def countWays(self, s):
        return self.solve(s, 0, len(s) - 1, True)
Enter fullscreen mode Exit fullscreen mode

countWays calls solve once, over the full string, asking specifically for the True count, since that's the actual question the problem is asking.

A Small Dry Run 

s = T ^ F
Index:  0   1   2
        T   ^   F
Enter fullscreen mode Exit fullscreen mode

The only operator sits at k = 1, so the left substring is s[0..0] = "T" and the right substring is s[2..2] = "F".

Left (T): leftTrue = 1 (it's literally T), leftFalse = 0.

Right (F): rightTrue = 0, rightFalse = 1 (it's literally F).

Combining with XOR's target-True formula:

target True = leftTrue * rightFalse + leftFalse * rightTrue
            = (1 * 1) + (0 * 0)
            = 1
Enter fullscreen mode Exit fullscreen mode

One way to make T ^ F evaluate to True, which checks out, since there's only one possible parenthesization for a two-operand expression in the first place, and it does evaluate to True.

MCM vs Palindrome Partitioning vs Boolean Parenthesization

MCM Palindrome Partitioning Boolean Parenthesization
Input Dimension array String Boolean expression string
State solve(i, j) solve(i, j) solve(i, j, isTrue)
k loop range(i, j) range(i, j) range(i+1, j, 2), operators only
Left/right subproblems One value each One value each Two values each (True count, False count)
Combining step left + right + arr[i-1]*arr[k]*arr[j] left + right + 1 Per-operator truth table, multiply and add
Aggregation across k min min += (sum across all valid splits)
Answer represents A minimum cost A minimum cut count A count of valid parenthesizations

The pattern holds across all three: boundaries i and j, a loop over valid split points k, subproblems solved on both sides, and a combination step that's specific to the problem. What changes each time is what the state actually needs to track, and how the two sides get combined once you have them. MCM and Palindrome Partitioning could get away with a single value per subproblem because they were optimizing one number. Boolean Parenthesization needs both True and False counts, because the operator's truth table decides which cross-combinations of the two sides actually matter.

Quick Revision 

solve(i, j, isTrue) = number of ways s[i..j] evaluates to isTrue

Base cases:
  if i > j: return 0
  if i == j: return 1 if s[i] matches isTrue, else 0

Transition:
  for k in range(i+1, j, 2):   # operators only
    leftTrue, leftFalse   = solve(i, k-1, True), solve(i, k-1, False)
    rightTrue, rightFalse = solve(k+1, j, True), solve(k+1, j, False)
    combine using s[k]'s truth table, add to ans

Initial call: solve(0, n-1, True)

The change from MCM and Palindrome Partitioning:
  state grows from (i, j) to (i, j, isTrue)
  each subproblem needs both True and False counts
  combining step is a truth table per operator, not a single formula
Enter fullscreen mode Exit fullscreen mode

What You Now Understand

Boolean Parenthesization keeps the exact same partitioning skeleton as MCM and Palindrome Partitioning, boundaries, a split point, subproblems on both sides, but it's the first problem in this family where a single number per subproblem genuinely isn't enough. The moment an operator like XOR needs to know both how a side can be True and how it can be False to figure out what the combination produces, the state has to grow to carry both. That's the real lesson here: the skeleton doesn't change, but the shape of what each subproblem needs to return depends entirely on what the combining step at the top actually requires.

The next chapter takes this same recursive solution and adds memoization to it, the same reasoning as before, except now the cache has to be keyed on three values instead of two, (i, j, isTrue), using either a dictionary or a structured 3D table.

Top comments (0)