Package g1801_1900.s1896_minimum_cost_to_change_the_final_value_of_expression

Class Solution

java.lang.Object

g1801_1900.s1896_minimum_cost_to_change_the_final_value_of_expression.Solution

public class Solution
extends Object

1896 - Minimum Cost to Change the Final Value of Expression.<p>Hard</p> <p>You are given a <strong>valid</strong> boolean expression as a string <code>expression</code> consisting of the characters <code>'1'</code>,<code>'0'</code>,<code>'&'</code> (bitwise <strong>AND</strong> operator),<code>'|'</code> (bitwise <strong>OR</strong> operator),<code>'('</code>, and <code>')'</code>.</p> <ul> <li>For example, <code>&quot;()1|1&quot;</code> and <code>&quot;(1)&()&quot;</code> are <strong>not valid</strong> while <code>&quot;1&quot;</code>, <code>&quot;(((1))|(0))&quot;</code>, and <code>&quot;1|(0&(1))&quot;</code> are <strong>valid</strong> expressions.</li> </ul> <p>Return <em>the <strong>minimum cost</strong> to change the final value of the expression</em>.</p> <ul> <li>For example, if <code>expression = &quot;1|1|(0&0)&1&quot;</code>, its <strong>value</strong> is <code>1|1|(0&0)&1 = 1|1|0&1 = 1|0&1 = 1&1 = 1</code>. We want to apply operations so that the <strong>new</strong> expression evaluates to <code>0</code>.</li> </ul> <p>The <strong>cost</strong> of changing the final value of an expression is the <strong>number of operations</strong> performed on the expression. The types of <strong>operations</strong> are described as follows:</p> <ul> <li>Turn a <code>'1'</code> into a <code>'0'</code>.</li> <li>Turn a <code>'0'</code> into a <code>'1'</code>.</li> <li>Turn a <code>'&'</code> into a <code>'|'</code>.</li> <li>Turn a <code>'|'</code> into a <code>'&'</code>.</li> </ul> <p><strong>Note:</strong> <code>'&'</code> does <strong>not</strong> take precedence over <code>'|'</code> in the <strong>order of calculation</strong>. Evaluate parentheses <strong>first</strong> , then in <strong>left-to-right</strong> order.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> expression = &ldquo;1&(0|1)&rdquo;</p> <p><strong>Output:</strong> 1</p> <p><strong>Explanation:</strong> We can turn &ldquo;1&(0|1)&rdquo; into &ldquo;1&(0&1)&rdquo; by changing the &lsquo;|&rsquo; to a &lsquo;&&rsquo; using 1 operation.</p> <p>The new expression evaluates to 0.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> expression = &ldquo;(0&0)&(0&0&0)&rdquo;</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> We can turn &ldquo;(0&0)&(0&0&0)&rdquo; into &ldquo;(0|1)|(0&0&0)&rdquo; using 3 operations.</p> <p>The new expression evaluates to 1.</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> expression = &ldquo;(0|(1|0&1))&rdquo;</p> <p><strong>Output:</strong> 1</p> <p><strong>Explanation:</strong> We can turn &ldquo;(0|(1|0&1))&rdquo; into &ldquo;(0|(0|0&1))&rdquo; using 1 operation.</p> <p>The new expression evaluates to 0.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= expression.length <= 10⁵</code></li> <li><code>expression</code> only contains <code>'1'</code>,<code>'0'</code>,<code>'&'</code>,<code>'|'</code>,<code>'('</code>, and <code>')'</code></li> <li>All parentheses are properly matched.</li> <li>There will be no empty parentheses (i.e: <code>&quot;()&quot;</code> is not a substring of <code>expression</code>).</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	minOperationsToFlip(String expression)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

minOperationsToFlip

public int minOperationsToFlip(String expression)