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).The key idea for #1896 Minimum Cost to Change the Final Value of Expression is to evaluate the boolean expression while tracking the minimum cost to make each subexpression evaluate to 0 or 1. Since the expression contains digits (0, 1), operators (&, |), and parentheses, a stack-based parsing approach works well.
For every subexpression, maintain a pair (cost0, cost1), representing the minimum cost to make the result 0 or 1. When combining two subexpressions with an operator, compute the resulting costs using logical rules. Also consider that changing an operator (e.g., & to |) or flipping a value contributes to the cost.
Parentheses help isolate subproblems, which can be solved using dynamic programming on the expression tree. By processing tokens sequentially and merging results when encountering operators or closing parentheses, we efficiently compute the minimum flip cost for the final expression value.
This approach runs in O(n) time with O(n) auxiliary space due to stack storage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack + Dynamic Programming on Expression | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
How many possible states are there for a given expression?
Is there a data structure that we can use to solve the problem optimally?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Dynamic programming helps track the minimum cost for both possible outcomes of every subexpression. Instead of recomputing possibilities, previously computed results are reused when combining expressions with operators.
Yes, problems involving expression parsing, boolean evaluation, and cost optimization appear in interviews at companies like Google, Amazon, and Meta. This problem tests stack usage, dynamic programming, and careful logical reasoning.
Stacks are ideal for parsing the expression and handling parentheses. Each stack entry can store the cost pair (cost to make 0, cost to make 1), which enables efficient combination of subexpressions during evaluation.
The optimal approach uses a stack combined with dynamic programming. For each subexpression, store the minimum cost required to make it evaluate to 0 or 1, and merge results based on the logical operator. This allows the entire expression to be evaluated in linear time.