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.
Description: Use a DFS approach to evaluate each sub-expression. Traverse the expression, and for each binary operation, calculate the cost of flipping the result by inspecting the preceding and succeeding values, along with the operation. Maintain a stack to manage parentheses properly. Each entry in the stack will comprise the current cost, number of required flips, and the results of sub-expressions.
This C solution initializes the parsing of the expression using a stack. Each stack element includes state information like current result, costs, and flip probabilities. Iteratively traverse each character in the expression, updating the stack based on evaluated conditions and operations.
Time Complexity: O(n) where n is the length of the expression.
Space Complexity: O(n) due to the stack.
Description: Implement a dynamic programming method to split the expression at each binary operator, computing minimal costs for flipping sub-expression results. Capture intermediate results in a table, indexing by part of the expression under current evaluation.
The approach dynamically parses sections of the input towards minimizing toggle costs. We can maintain a table mimicking a recursive call structure, with costs per evaluated expression sequence calculated iteratively.
Time Complexity: O(n^3) for the combinatorial splits of expressions.
Space Complexity: O(n^2) to store intermediate calculations.
| Approach | Complexity |
|---|---|
| DFS Based Approach | Time Complexity: O(n) where n is the length of the expression. |
| Dynamic Programming Approach | Time Complexity: O(n^3) for the combinatorial splits of expressions. |
| 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 |
LeetCode 1896. Minimum Cost to Change the Final Value of Expression • Happy Coding • 1,051 views views
Watch 4 more video solutions →Practice Minimum Cost to Change the Final Value of Expression with our built-in code editor and test cases.
Practice on FleetCode