# Minimum Cost to Change the Final Value of Expression
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-to-change-the-final-value-of-expression)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-change-the-final-value-of-expression
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String, Stack
---
## Problem
You are given a **valid** boolean expression as a string `expression` consisting of the characters `'1'`,`'0'`,`'&'` (bitwise **AND** operator),`'|'` (bitwise **OR** operator),`'('`, and `')'`.

* For example, `"()1|1"` and `"(1)&()"` are **not valid** while `"1"`, `"(((1))|(0))"`, and `"1|(0&(1))"` are **valid** expressions.

Return _the **minimum cost** to change the final value of the expression_.

* For example, if `expression = "1|1|(0&0)&1"`, its **value** is `1|1|(0&0)&1 = 1|1|0&1 = 1|0&1 = 1&1 = 1`. We want to apply operations so that the **new** expression evaluates to `0`.

The **cost** of changing the final value of an expression is the **number of operations** performed on the expression. The types of **operations** are described as follows:

* Turn a `'1'` into a `'0'`.
* Turn a `'0'` into a `'1'`.
* Turn a `'&'` into a `'|'`.
* Turn a `'|'` into a `'&'`.

**Note:** `'&'` does **not** take precedence over `'|'` in the **order of calculation**. Evaluate parentheses **first**, then in **left-to-right** order.

**Example 1:**

**Input:** expression = "1&(0|1)"
**Output:** 1
**Explanation:** We can turn "1&(0**|**1)" into "1&(0**&**1)" by changing the '|' to a '&' using 1 operation.
The new expression evaluates to 0. 

**Example 2:**

**Input:** expression = "(0&0)&(0&0&0)"
**Output:** 3
**Explanation:** We can turn "(0**&0**)**&**(0&0&0)" into "(0**|1**)**|**(0&0&0)" using 3 operations.
The new expression evaluates to 1.

**Example 3:**

**Input:** expression = "(0|(1|0&1))"
**Output:** 1
**Explanation:** We can turn "(0|(**1**|0&1))" into "(0|(**0**|0&1))" using 1 operation.
The new expression evaluates to 0.

**Constraints:**

* `1 <= expression.length <= 105`
* `expression` only contains `'1'`,`'0'`,`'&'`,`'|'`,`'('`, and `')'`
* All parentheses are properly matched.
* There will be no empty parentheses (i.e: `"()"` is not a substring of `expression`).

# Approaches
## Recursive Parsing with Memoization
This approach uses recursion to solve the problem, mirroring the recursive nature of the expression itself. We define a function that takes a subexpression and returns the minimum cost to make it evaluate to 0 and the minimum cost to make it evaluate to 1. To avoid recomputing the same subproblem, we use memoization.
**Time:** O(N^2), where N is the length of the expression. For each subproblem of length `k`, we scan it in O(k) time to find the split point. The sum of work across all subproblems leads to an O(N^2) complexity in the worst case (e.g., for expressions like `1&1&1...&1`). · **Space:** O(N^2), where N is the length of the expression. The memoization can store up to O(N^2) subproblems, and the sum of the lengths of these subproblem strings can also be O(N^2). The recursion depth can go up to O(N).
**Pros:** The recursive structure of the solution closely matches the recursive structure of the problem, making it conceptually straightforward.
**Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will result in a Time Limit Exceeded error.; The space complexity of O(N^2) can be very high.; Repeatedly creating substrings is inefficient in Java.
### Explanation
We can define a recursive function, for instance `solve(expression_string)`, which computes a pair of values: the minimum cost to make the expression evaluate to 0, and the minimum cost to make it evaluate to 1. The base cases for the recursion are single-digit strings '0' and '1'. For any other expression, we find the main operator (the last one evaluated according to the rules) and split the expression into two operands. We then make recursive calls on these operands. The results from the recursive calls are combined based on the operator. For example, to make `E1 & E2` evaluate to 1, we must make both `E1` and `E2` evaluate to 1, so the cost is the sum of their costs to become 1. We also consider the option of changing the operator itself (e.g., `&` to `|`) for an additional cost of 1. Since the same subexpression can appear multiple times, we use memoization to store and reuse the results, effectively turning the recursion into dynamic programming.

```java
class Solution {
    private Map<String, int[]> memo;

    public int minOperationsToFlip(String expression) {
        memo = new HashMap<>();
        int[] costs = solve(expression);
        // The cost to achieve the original value is 0.
        // The cost to flip is the other value in the pair.
        // So, the answer is the maximum of the two costs.
        return Math.max(costs[0], costs[1]);
    }

    private int[] solve(String expr) {
        if (memo.containsKey(expr)) {
            return memo.get(expr);
        }
        if (expr.equals("0")) {
            return new int[]{0, 1}; // {cost_for_0, cost_for_1}
        }
        if (expr.equals("1")) {
            return new int[]{1, 0};
        }

        int balance = 0;
        int splitIndex = -1;
        // Find the last operator at parenthesis level 0
        for (int i = expr.length() - 1; i >= 0; i--) {
            char c = expr.charAt(i);
            if (c == ')') balance++;
            else if (c == '(') balance--;
            else if (balance == 0 && (c == '&' || c == '|')) {
                splitIndex = i;
                break;
            }
        }

        int[] result;
        if (splitIndex == -1) { // Expression is wrapped in parentheses
            result = solve(expr.substring(1, expr.length() - 1));
        } else {
            char op = expr.charAt(splitIndex);
            String leftExpr = expr.substring(0, splitIndex);
            String rightExpr = expr.substring(splitIndex + 1);

            int[] leftCosts = solve(leftExpr);
            int[] rightCosts = solve(rightExpr);
            int c1_0 = leftCosts[0], c1_1 = leftCosts[1];
            int c2_0 = rightCosts[0], c2_1 = rightCosts[1];

            result = new int[2];
            if (op == '&') {
                result[0] = Math.min(Math.min(c1_0, c2_0), 1 + c1_0 + c2_0);
                result[1] = Math.min(c1_1 + c2_1, 1 + Math.min(c1_1, c2_1));
            } else { // op == '|'
                result[0] = Math.min(c1_0 + c2_0, 1 + Math.min(c1_0, c2_0));
                result[1] = Math.min(Math.min(c1_1, c2_1), 1 + c1_1 + c2_1);
            }
        }

        memo.put(expr, result);
        return result;
    }
}
```
### Algorithm
- The core idea is to use recursion to break down the expression into smaller subproblems. We define a function, say `solve(subExpression)`, that computes the minimum costs.
- The state for our recursion/dynamic programming will be a pair of values: `{cost_to_evaluate_to_0, cost_to_evaluate_to_1}`.
- **Base Cases:**
  - If `subExpression` is `'0'`, the cost to make it `0` is `0`, and to make it `1` is `1`. So we return `{0, 1}`.
  - If `subExpression` is `'1'`, the cost to make it `0` is `1`, and to make it `1` is `0`. So we return `{1, 0}`.
- **Recursive Step:**
  - For a complex `subExpression`, we first need to find its main operator. Due to the left-to-right evaluation rule (with parentheses taking precedence), the main operator is the last `&` or `|` that is not enclosed in parentheses.
  - We can find this by scanning the subexpression from right to left, keeping track of the parenthesis nesting level. The first operator found at level 0 is our split point.
  - If no such operator is found, the expression must be fully enclosed in parentheses (e.g., `(1&0)`). In this case, we strip the outer parentheses and recurse on the inner part.
  - Once we split the expression `E` into `E1 op E2`, we recursively call `solve(E1)` and `solve(E2)` to get their respective cost pairs, say `{c1_0, c1_1}` and `{c2_0, c2_1}`.
  - We then combine these results using predefined formulas to calculate the costs for `E`.
- **Combining Results:** For an expression `E1 op E2`:
  - If `op` is `&`:
    - `cost(E, 0) = min(min(c1_0, c2_0), 1 + c1_0 + c2_0)`
    - `cost(E, 1) = min(c1_1 + c2_1, 1 + min(c1_1, c2_1))`
  - If `op` is `|`:
    - `cost(E, 0) = min(c1_0 + c2_0, 1 + min(c1_0, c2_0))`
    - `cost(E, 1) = min(min(c1_1, c2_1), 1 + c1_1 + c2_1)`
- **Memoization:** To avoid recomputing results for the same subexpressions, we use a hash map or a 2D array to store the results of `solve(subExpression)`.

## Single-Pass Stack-based Evaluation
A more efficient approach is to use a method similar to the standard algorithm for evaluating arithmetic expressions: a two-stack approach. This allows us to parse and compute the costs in a single pass over the expression, achieving linear time complexity.
**Time:** O(N), where N is the length of the expression. Each character, value, and operator is pushed onto and popped from the stacks at most once. · **Space:** O(N), where N is the length of the expression. In the worst-case scenario (e.g., `1&1&...&1` or `((...))`), the stacks can grow to a size proportional to N.
**Pros:** Optimal time complexity of O(N), which passes for the given constraints.; Optimal space complexity of O(N).; It's an iterative solution, so it avoids potential stack overflow issues with deep recursion on very long expressions.
**Cons:** The implementation can be more complex than a direct recursive solution, requiring careful handling of stacks and operator precedence rules.
### Explanation
We can process the expression iteratively in one pass. We use a stack for operands (which in our case are the `{cost_to_0, cost_to_1}` pairs) and another stack for operators. As we scan the expression string:
- Numbers (`'0'`, `'1'`) are converted to their base cost pairs and pushed onto the value stack.
- `'('` is pushed onto the operator stack.
- An operator (`'&'`, `'|'`) triggers the evaluation of the previous operator on the stack (if it's not a `'('`), due to the left-to-right evaluation rule. Then, the current operator is pushed.
- `')'` triggers evaluation of all operators until the matching `'('` is found.

This process builds up the costs for larger and larger subexpressions from the bottom up. After the entire string is processed, any remaining operators on the stack are evaluated. The final answer is on top of the value stack. If the final cost pair is `{c0, c1}`, the original value of the expression corresponds to the one with zero cost. For instance, if `c1` is 0, the expression evaluates to 1, and the cost to flip it to 0 is `c0`. A simple way to get the answer is `max(c0, c1)`.

```java
class Solution {
    public int minOperationsToFlip(String expression) {
        Stack<int[]> valuesStack = new Stack<>(); // {cost_to_0, cost_to_1}
        Stack<Character> opsStack = new Stack<>();

        for (char c : expression.toCharArray()) {
            if (c == '0') {
                valuesStack.push(new int[]{0, 1});
            } else if (c == '1') {
                valuesStack.push(new int[]{1, 0});
            } else if (c == '(') {
                opsStack.push(c);
            } else if (c == ')') {
                while (!opsStack.isEmpty() && opsStack.peek() != '(') {
                    evaluate(valuesStack, opsStack);
                }
                opsStack.pop(); // Pop '('
            } else { // Operator '&' or '|'
                while (!opsStack.isEmpty() && opsStack.peek() != '(') {
                    evaluate(valuesStack, opsStack);
                }
                opsStack.push(c);
            }
        }

        while (!opsStack.isEmpty()) {
            evaluate(valuesStack, opsStack);
        }

        int[] finalCosts = valuesStack.pop();
        return Math.max(finalCosts[0], finalCosts[1]);
    }

    private void evaluate(Stack<int[]> valuesStack, Stack<Character> opsStack) {
        char op = opsStack.pop();
        int[] rightCosts = valuesStack.pop();
        int[] leftCosts = valuesStack.pop();

        int c1_0 = leftCosts[0], c1_1 = leftCosts[1];
        int c2_0 = rightCosts[0], c2_1 = rightCosts[1];

        int[] result = new int[2];
        if (op == '&') {
            // Cost to get 0: min(make one operand 0, change op to | and make both 0)
            result[0] = Math.min(Math.min(c1_0, c2_0), 1 + c1_0 + c2_0);
            // Cost to get 1: min(make both operands 1, change op to | and make one 1)
            result[1] = Math.min(c1_1 + c2_1, 1 + Math.min(c1_1, c2_1));
        } else { // op == '|'
            // Cost to get 0: min(make both operands 0, change op to & and make one 0)
            result[0] = Math.min(c1_0 + c2_0, 1 + Math.min(c1_0, c2_0));
            // Cost to get 1: min(make one operand 1, change op to & and make both 1)
            result[1] = Math.min(Math.min(c1_1, c2_1), 1 + c1_1 + c2_1);
        }
        valuesStack.push(result);
    }
}
```
### Algorithm
- This approach uses two stacks: one for values (`valuesStack`) and one for operators (`opsStack`). The `valuesStack` will store pairs of `{cost_to_make_0, cost_to_make_1}`.
- We iterate through the expression character by character from left to right.
- If the character is `'0'` or `'1'`, we push the corresponding base cost pair (`{0, 1}` for `'0'`, `{1, 0}` for `'1'`) onto the `valuesStack`.
- If the character is `'('`, we push it onto the `opsStack`.
- If the character is `')'`, we evaluate operations from the `opsStack` until we find the matching `'('`. We pop the `'('` but do not use it in calculations.
- If the character is an operator (`'&'` or `'|'`), we first check the top of the `opsStack`. Because `&` and `|` have the same precedence and are evaluated left-to-right, we must evaluate any pending operator at the top of the stack (as long as it's not a `'('`). After evaluating, we push the current operator onto `opsStack`.
- The evaluation step involves popping one operator from `opsStack` and two cost pairs from `valuesStack`. We then compute the new cost pair using the combination formulas and push the result back onto `valuesStack`.
- After iterating through the entire expression, we evaluate any remaining operators in the `opsStack`.
- The final result will be the single cost pair left on the `valuesStack`. The cost to flip the expression's value is the maximum of the two values in this pair, as one will be 0 (the cost to obtain the original value) and the other will be the minimum cost to change it.

# Solutions
### Java

```java
class Solution {
public
  int minOperationsToFlip(String expression) {
    Deque<Integer> numStack = new LinkedList<Integer>();
    Deque<Integer> opStack = new LinkedList<Integer>();
    Deque<Character> signStack = new LinkedList<Character>();
    int length = expression.length();
    for (int i = 0; i < length; i++) {
      char c = expression.charAt(i);
      if (Character.isDigit(c)) {
        numStack.push((int)(c - '0'));
        opStack.push(1);
      } else if (c == ')')
        signStack.pop();
      else {
        signStack.push(c);
        continue;
      }
      if (numStack.size() > 1 && signStack.peek() != '(') {
        int num2 = numStack.pop();
        int num1 = numStack.pop();
        int op2 = opStack.pop();
        int op1 = opStack.pop();
        char sign = signStack.pop();
        int[] ops = minOp(num1, num2, op1, op2, sign);
        numStack.push(ops[0]);
        opStack.push(ops[1]);
      }
    }
    return opStack.pop();
  }
public
  int[] minOp(int num1, int num2, int op1, int op2, char sign) {
    if (sign == '&') {
      if (num1 == 1 && num2 == 1)
        return new int[]{1, Math.min(op1, op2)};
      else if (num1 == 0 && num2 == 0)
        return new int[]{0, Math.min(op1, op2) + 1};
      else
        return new int[]{0, 1};
    } else {
      if (num1 == 0 && num2 == 0)
        return new int[]{0, Math.min(op1, op2)};
      else if (num1 == 1 && num2 == 1)
        return new int[]{1, Math.min(op1, op2) + 1};
      else
        return new int[]{1, 1};
    }
  }
}

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/minimum-cost-to-change-the-final-value-of-expression/ // Time: O(N) // Space: O(N) // Ref: https://www.bilibili.com/video/BV1yU4y1V79x class Solution { stack < vector < int >> num ; stack < char > op ; void eval () { auto b = num . top (); num . pop (); auto a = num . top (); num . pop (); char c = op . top (); op . pop (); if ( c == '&' ) { num . push ({ min ({ a [ 0 ] + b [ 0 ], a [ 1 ] + b [ 0 ], a [ 0 ] + b [ 1 ] }), min ({ a [ 1 ] + b [ 1 ], a [ 1 ] + b [ 0 ] + 1 , a [ 0 ] + b [ 1 ] + 1 , a [ 1 ] + b [ 1 ] + 1 }) }); } else { num . push ({ min ({ a [ 0 ] + b [ 0 ], a [ 0 ] + b [ 1 ] + 1 , a [ 1 ] + b [ 0 ] + 1 , a [ 0 ] + b [ 0 ] + 1 }), min ({ a [ 1 ] + b [ 1 ], a [ 1 ] + b [ 0 ], a [ 0 ] + b [ 1 ] }) }); } } public: int minOperationsToFlip ( string s ) { for ( char c : s ) { if ( isdigit ( c )) { if ( c == '0' ) num . push ({ 0 , 1 }); else num . push ({ 1 , 0 }); } else if ( c == '(' ) { op . push ( c ); } else if ( c == ')' ) { while ( op . top () != '(' ) eval (); op . pop (); } else { while ( op . size () && op . top () != '(' ) eval (); op . push ( c ); } } while ( op . size ()) eval (); return max ( num . top ()[ 0 ], num . top ()[ 1 ]); } };
```