• Before moving any further it is important for you to know about the behavior of operators very well.
• Expressions can be of 3 types:
  • ((left) & (right))
  • ((left) | (right))
  • ((left) ^ (right))
  Let say that the left can yield ltc (left true count) number of true and lfc (left false count) number of false. And right can yield rtc (right true count) number of true and rfc (right false count) number of false.
• Type-1: ((left) & (right)); If the operator is '&' then the expression can be true for (ltc * rtc) number of times and it can be false for ((ltc * rfc) + (lfc * rfc) +(lfc * rtc)) number of times.
• Type-2: ((left) | (right)); if the operator is '|' then the expression can be true for ((ltc * rtc) + (ltc * rfc) +(lfc * rtc)) number of times and it can be false for (lfc * rfc) number of times.
• Type-3: ((left) ^ (right)); if the operator is '^' then the expression can be true for ((ltc * rfc) + (lfc * rtc)) number of times and it can be false for ((ltc * rtc) + (lfc * rfc)) number of times.
  For more clarity of the above table watch this part of the lecture video.
• In order to solve this problem we will use the Gap Strategy of dynamic programming.
  • In this strategy we use a 2D array of n x n and then we assign some meaning to the cells of the 2D array.
  • After that we fill the matrix diagonally, moving from smaller problems to the bigger problem.
• Let's try to build the solution using an example where String-1 = TFTF and String-2 = &|^.
• In this problem we need two 2d arrays dpt[][] (dp storing count of tue) and dpf[][] (dp storing count of false) of (n x n), where n is the length of string-1.
• Trivial case for these matrices would be the main diagonal where the cells represent the scenario where there is only one character contributing to the expression which is either a T or F.
• So in dpt we will store 1 corresponding to T(s) and 0 corresponding to F(s) in the main diagonal (when gap = 0) because for boolean value T, there is one way we can parenthesize T such that it evaluates True whereas for F, there is no way we can parenthesize it such that it evaluates True.
• However in dpf we will store 1 corresponding to F(s) and 0 corresponding to T(s) in the main diagonal (when gap = 0) because for boolean value F, there is one way we can parenthesize F such that it evaluates False whereas for T, there is no way we can parenthesize it such that it evaluates False.
• Now to fill the rest of the diagonals of both the matrices we need to use the formulas corresponding to the operator.
• However in the next diagonal we can also fill the matrices directly as there is only one operator. So we can use either way to fill it.
• First cell of this diagonal is for (T&F) which results in true in zero ways and false in only one way so we store 0 corresponding to this cell in dpt and 1 in dpf.
• Second cell for this diagonal is for (F|T) which results in true in only one way and false in zero way, so we store 1 corresponding to this cell in dpt and 0 in dpf.
• Last cell corresponds to (T^F) which gives true in one way and false in zero ways, so we store 1 corresponding to this cell in dpt and 0 in dpf.
  For more clarity of the above part watch this part of the lecture video.
• Let's jump to the next diagonal (at gap = 2).
• In this diagonal, first cell corresponds to (T&F|T). This can split in 2 ways ((T&F) | (T)) and ((T) & (F|T)).
• If you observe then we have the count corresponding to all the sub-expressions of these 2 expressions. So we can finally use the formulas of type (left | right) and (left & right) for calculating the result rather than doing it manually. Refer the below diagram for understanding of the math of the formulas.
• In the diagram, we have portioned the expression at the operators to consider all possibilities.
• In (T&F|T), first we partition the expression at '&' and then at '|'.
• Then for each expression we calculate the count of true and false for using the respective formula.
  For more clarity of the above part watch this part of the lecture video.
• Similarly we can fill the next cell of this diagonal which correspond to the expression (F|T^F), in both the matrices using the formulas and the previously filled matrices by partitioning the expression at the operators '|' and then '^' for exploring all possibilities.
  For more clarity of the above part watch this part of the lecture video.
• Finally we move to the last diagonal with only one cell which will store the final answer of this.
• Complete and final expression for this cell is (T&F|T^F). We can partition this expression at three points. Yes, at all three operators like ((T) & (F|T^F)), ((T&F) | (T^F)) and ((T&F|T) ^ (F)). Now each of these expressions can use the formulas of type-1, 2 and 3 respectively for calculating the count of true and false.
  For better mathematical clarification of the above part watch this part of the lecture video and refer to the above diagram.

First of all, we need to define two 2D arrays of n x n (where n is the length of the string-1) to store the count of true and false; let's call them 't' and 'f'. Then to use the gap strategy we need to run a for loop starting from 0 until the gap is less than n. And then we need to initialize two more variables si (starting index) and ei (ending index).

Now inside this for loop, we will run a while loop to fill both the 2D arrays 't' and 'f' diagonally.

On entering the while loop; first of all we handle the trivial case (base case). If the gap is zero then we check if the character at si in string-1 is a 'T', if yes then we put 1 at t[si][ei], if not then we put 0 at t[si][ei].

After that we check if the character at si in string-1 is a 'F', if yes then we put 1 at f[si][ei], if not then we put 0 at f[si][ei].

And if the gap is some other value than 0 then we handle the cases using the formulas and the values stored in 't' and 'f' so far.

For every sub-expression it is important that we consider all the cases by partitioning the expression at each operator; to do so we use another for loop initialized with cp to si until cp is less than ei.

Then we capture the character present at cp in string-2 (operator at which partition is done).

After that we check whether the operator is '&' or '|' or '^'. Then we follow the respective condition's further steps.

In further steps we have coded the formulas (same that we have analyzed already) for calculating the count of true and false for each of the two 2D arrays.

For more clarity of the code, watch part of the video.