Boolean Parenthesization

"""
Intuition for Boolean Parenthesization (Step-by-Step Breakdown)

Step 1: Identify the Problem Type
---------------------------------
This is a variation of 'Matrix Chain Multiplication' (MCM). We are given
an expression and we need to place brackets (parenthesize) in different
ways to get a result. Whenever we have multiple ways to 'split' an
expression, we think of the MCM pattern.

Step 2: Define the Range (i and j)
----------------------------------
To solve any MCM-style problem, we need a left boundary 'i' and a
right boundary 'j'.
- s = "T ^ F & T"
- i starts at 0 (first operand), j starts at n-1 (last operand).

Step 3: Finding the 'k' (The Split Point)
-----------------------------------------
Where can we break the expression? We can only break at the operators
(^, &, |).
- Operators are always at odd indices (1, 3, 5...).
- So, our loop for 'k' will start at i+1 and go to j-1, incrementing
  by 2 (k += 2) to always land on an operator.

Step 4: The Recursive 'Aha!' Moment
------------------------------------
Unlike standard MCM where we just return one value (like min cost),
here the result of an operator depends on both True and False values
of its children.
Example: For (Left) XOR (Right) to be True:
   - Left must be True AND Right must be False
   OR
   - Left must be False AND Right must be True

Therefore, our function must ask for TWO things from every sub-problem:
1. Number of ways to make the left/right side TRUE.
2. Number of ways to make the left/right side FALSE.

Step 5: Base Cases
------------------
- If i > j: Empty string, 0 ways.
- If i == j: Single character.
    - If target is True: return 1 if s[i]=='T' else 0
    - If target is False: return 1 if s[i]=='F' else 0

Step 6: Combine Results (The Logic Gates)
-----------------------------------------
For every split at operator s[k], we calculate:
- lT (Left True), lF (Left False)
- rT (Right True), rF (Right False)

Based on s[k], we update our 'ans':
- If '&':
    - Ways to be True: lT * rT
    - Ways to be False: (lT*rF) + (lF*rT) + (lF*rF)
- If '|':
    - Ways to be True: (lT*rT) + (lT*rF) + (lF*rT)
    - Ways to be False: lF * rF
- If '^':
    - Ways to be True: (lT*rF) + (lF*rT)
    - Ways to be False: (lT*rT) + (lF*rF)

Step 7: Optimization (Memoization)
----------------------------------
Since (i, j, target) repeats many times in the recursion tree,
we store the result in a map or a 3D array to avoid TLE.
"""

from math import inf
def fun(s, i, j, dp, target):
    if i > j:
        return 0

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

    if dp[i][j][target] != -1:
        return dp[i][j][target]

    ans = 0
    for k in range(i+1, j, 2):
        lt = fun(s, i, k-1, dp, True)
        lf = fun(s, i, k-1, dp, False)
        rt = fun(s, k+1, j, dp, True)
        rf = fun(s, k+1, j, dp, False)
        if s[k] == '&':
            if target:
                ans += lt * rt
            else:
                ans += lt * rf + lf * rt + lf * rf

        elif s[k] == '|':
            if target:
                ans += lt * rt + lt * rf + lf * rt
            else:
                ans += lf * rf

        else:  # '^'
            if target:
                ans += lt * rf + lf * rt
            else:
                ans += lt * rt + lf * rf

    dp[i][j][target] = ans
    return ans

class Solution:
    def countWays(self, s):
        n = len(s)
        dp = [[[-1]*2 for _ in range(n)] for _ in range(n)]
        return fun(s, 0, n-1, dp, True)