Watch 5 video solutions for Minimum Cost to Change the Final Value of Expression, a hard level problem involving Math, String, Dynamic Programming. This walkthrough by Happy Coding has 1,051 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a valid boolean expression as a string expression consisting of the characters '1','0','&' (bitwise AND operator),'|' (bitwise OR operator),'(', and ')'.
"()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.
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:
'1' into a '0'.'0' into a '1'.'&' into 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 <= 105expression only contains '1','0','&','|','(', and ')'"()" is not a substring of expression).Problem Overview: You are given a boolean expression containing 0, 1, operators & and |, and parentheses. Each change (flipping a digit or switching an operator) costs 1. The task is to compute the minimum cost required to change the final evaluated value of the entire expression.
Approach 1: DFS Based Expression Tree Evaluation (O(n) time, O(n) space)
Parse the expression into a tree and evaluate it using DFS. For every subexpression, track two values: the minimum cost to make the subexpression evaluate to 0 and the minimum cost to make it evaluate to 1. Leaf nodes (0 or 1) have trivial costs: the current value costs 0, flipping it costs 1. For internal nodes, combine the results from the left and right children based on the operator. If the operator is &, producing 1 requires both sides to be 1; producing 0 can be done through multiple combinations or by flipping the operator to |. The DFS propagates the minimum cost pairs upward. The final answer is the cost needed to flip the computed result at the root.
This approach mirrors how expression trees are evaluated and keeps the logic local to each node. It works well when you want a clear structural interpretation of the expression. The recursive traversal ensures each character is processed once, giving O(n) time complexity and O(n) space due to recursion stack and tree representation.
Approach 2: Stack + Dynamic Programming on Subexpressions (O(n) time, O(n) space)
The more common solution avoids explicitly building a tree. Instead, scan the string and evaluate it using stacks, similar to standard expression evaluation. Each operand pushed to the stack stores a pair (cost0, cost1), representing the minimum cost to make that subexpression evaluate to 0 or 1. When an operator and two operands are ready to combine (or when closing a parenthesis), compute the new pair using transition rules for & and |.
For example, with operator &, achieving 1 requires both sides to become 1, while achieving 0 may come from multiple combinations or by flipping the operator to |. Dynamic programming is applied at every merge step by selecting the minimum cost among valid combinations. Parentheses are handled naturally by evaluating the stack until the matching opening bracket appears. The final pair for the entire expression directly gives the cost to flip the result.
This method treats each subexpression as a DP state and processes the string in a single pass. Because each character participates in a constant amount of work, the complexity remains O(n) time and O(n) space. It heavily relies on concepts from string parsing, stack-based expression evaluation, and dynamic programming.
Recommended for interviews: The stack + DP approach is what most interviewers expect. It demonstrates understanding of expression parsing and state transitions while keeping the complexity optimal at O(n). Discussing the DFS tree version first can show conceptual clarity, but implementing the stack-based DP usually signals stronger problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Based Expression Tree | O(n) | O(n) | When modeling the expression explicitly as a tree and combining results via recursive DFS |
| Stack + Dynamic Programming | O(n) | O(n) | General case and most efficient implementation for parsing and evaluating expressions |