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 theminimum 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 thenew 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.

Examples

Example 1

1
2
3
4

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

1
2
3
4

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

1
2
3
4

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 <= 10^5
  • 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).

Solution

Method 1 – Dynamic Programming with Stack

Intuition

We parse the expression recursively, keeping track of the minimum cost to flip the result to 0 or 1 at each subexpression. For each operator, we combine the costs from its left and right children according to the operator’s logic, and use a stack to handle parentheses.

Approach

  1. Use a stack to parse the expression and evaluate subexpressions.
  2. For each operand (‘0’ or ‘1’), store the cost to make it 0 and 1.
  3. For each operator (’&’ or ‘|’), combine the costs from left and right:
    • For ‘&’:
      • To get 1: both sides must be 1.
      • To get 0: either side can be 0.
    • For ‘|’:
      • To get 0: both sides must be 0.
      • To get 1: either side can be 1.
  4. For each subexpression, store the minimum cost to make it 0 and 1.
  5. At the end, return the cost to flip the final value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
public:
    int minOperationsToFlip(string expr) {
        stack<pair<int,int>> stk;
        stack<char> ops;
        auto merge = [](pair<int,int> a, pair<int,int> b, char op) {
            if (op == '&') {
                int to1 = a.second + b.second;
                int to0 = min(a.first, b.first);
                if (a.first == b.first) to0++;
                return make_pair(to0, to1);
            } else {
                int to0 = a.first + b.first;
                int to1 = min(a.second, b.second);
                if (a.second == b.second) to1++;
                return make_pair(to0, to1);
            }
        };
        for (char c : expr) {
            if (c == '0') stk.push({0,1});
            else if (c == '1') stk.push({1,0});
            else if (c == '(') ops.push(c);
            else if (c == ')') {
                while (ops.top() != '(') {
                    auto b = stk.top(); stk.pop();
                    auto a = stk.top(); stk.pop();
                    char op = ops.top(); ops.pop();
                    stk.push(merge(a, b, op));
                }
                ops.pop();
            } else if (c == '&' || c == '|') {
                while (!ops.empty() && ops.top() != '(') {
                    auto b = stk.top(); stk.pop();
                    auto a = stk.top(); stk.pop();
                    char op = ops.top(); ops.pop();
                    stk.push(merge(a, b, op));
                }
                ops.push(c);
            }
        }
        while (!ops.empty()) {
            auto b = stk.top(); stk.pop();
            auto a = stk.top(); stk.pop();
            char op = ops.top(); ops.pop();
            stk.push(merge(a, b, op));
        }
        auto res = stk.top();
        return max(res.first, res.second);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

func minOperationsToFlip(expr string) int {
    type pair struct{ zero, one int }
    stk := []pair{}
    ops := []byte{}
    merge := func(a, b pair, op byte) pair {
        if op == '&' {
            to1 := a.one + b.one
            to0 := min(a.zero, b.zero)
            if a.zero == b.zero { to0++ }
            return pair{to0, to1}
        } else {
            to0 := a.zero + b.zero
            to1 := min(a.one, b.one)
            if a.one == b.one { to1++ }
            return pair{to0, to1}
        }
    }
    for i := 0; i < len(expr); i++ {
        c := expr[i]
        if c == '0' { stk = append(stk, pair{0,1}) }
        else if c == '1' { stk = append(stk, pair{1,0}) }
        else if c == '(' { ops = append(ops, c) }
        else if c == ')' {
            for ops[len(ops)-1] != '(' {
                b := stk[len(stk)-1]; stk = stk[:len(stk)-1]
                a := stk[len(stk)-1]; stk = stk[:len(stk)-1]
                op := ops[len(ops)-1]; ops = ops[:len(ops)-1]
                stk = append(stk, merge(a, b, op))
            }
            ops = ops[:len(ops)-1]
        } else if c == '&' || c == '|' {
            for len(ops) > 0 && ops[len(ops)-1] != '(' {
                b := stk[len(stk)-1]; stk = stk[:len(stk)-1]
                a := stk[len(stk)-1]; stk = stk[:len(stk)-1]
                op := ops[len(ops)-1]; ops = ops[:len(ops)-1]
                stk = append(stk, merge(a, b, op))
            }
            ops = append(ops, c)
        }
    }
    for len(ops) > 0 {
        b := stk[len(stk)-1]; stk = stk[:len(stk)-1]
        a := stk[len(stk)-1]; stk = stk[:len(stk)-1]
        op := ops[len(ops)-1]; ops = ops[:len(ops)-1]
        stk = append(stk, merge(a, b, op))
    }
    res := stk[len(stk)-1]
    if res.zero > res.one { return res.zero } else { return res.one }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
    public int minOperationsToFlip(String expr) {
        Stack<int[]> stk = new Stack<>();
        Stack<Character> ops = new Stack<>();
        for (char c : expr.toCharArray()) {
            if (c == '0') stk.push(new int[]{0,1});
            else if (c == '1') stk.push(new int[]{1,0});
            else if (c == '(') ops.push(c);
            else if (c == ')') {
                while (ops.peek() != '(') {
                    int[] b = stk.pop(), a = stk.pop();
                    char op = ops.pop();
                    stk.push(merge(a, b, op));
                }
                ops.pop();
            } else if (c == '&' || c == '|') {
                while (!ops.isEmpty() && ops.peek() != '(') {
                    int[] b = stk.pop(), a = stk.pop();
                    char op = ops.pop();
                    stk.push(merge(a, b, op));
                }
                ops.push(c);
            }
        }
        while (!ops.isEmpty()) {
            int[] b = stk.pop(), a = stk.pop();
            char op = ops.pop();
            stk.push(merge(a, b, op));
        }
        int[] res = stk.peek();
        return Math.max(res[0], res[1]);
    }
    int[] merge(int[] a, int[] b, char op) {
        if (op == '&') {
            int to1 = a[1] + b[1];
            int to0 = Math.min(a[0], b[0]);
            if (a[0] == b[0]) to0++;
            return new int[]{to0, to1};
        } else {
            int to0 = a[0] + b[0];
            int to1 = Math.min(a[1], b[1]);
            if (a[1] == b[1]) to1++;
            return new int[]{to0, to1};
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Solution {
    fun minOperationsToFlip(expr: String): Int {
        data class Pair(val zero: Int, val one: Int)
        val stk = ArrayDeque<Pair>()
        val ops = ArrayDeque<Char>()
        fun merge(a: Pair, b: Pair, op: Char): Pair {
            return if (op == '&') {
                val to1 = a.one + b.one
                var to0 = minOf(a.zero, b.zero)
                if (a.zero == b.zero) to0++
                Pair(to0, to1)
            } else {
                val to0 = a.zero + b.zero
                var to1 = minOf(a.one, b.one)
                if (a.one == b.one) to1++
                Pair(to0, to1)
            }
        }
        for (c in expr) {
            when (c) {
                '0' -> stk.addLast(Pair(0,1))
                '1' -> stk.addLast(Pair(1,0))
                '(' -> ops.addLast(c)
                ')' -> {
                    while (ops.last() != '(') {
                        val b = stk.removeLast()
                        val a = stk.removeLast()
                        val op = ops.removeLast()
                        stk.addLast(merge(a, b, op))
                    }
                    ops.removeLast()
                }
                '&', '|' -> {
                    while (ops.isNotEmpty() && ops.last() != '(') {
                        val b = stk.removeLast()
                        val a = stk.removeLast()
                        val op = ops.removeLast()
                        stk.addLast(merge(a, b, op))
                    }
                    ops.addLast(c)
                }
            }
        }
        while (ops.isNotEmpty()) {
            val b = stk.removeLast()
            val a = stk.removeLast()
            val op = ops.removeLast()
            stk.addLast(merge(a, b, op))
        }
        val res = stk.last()
        return maxOf(res.zero, res.one)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def minOperationsToFlip(self, expr: str) -> int:
        stk = []
        ops = []
        def merge(a: tuple[int,int], b: tuple[int,int], op: str) -> tuple[int,int]:
            if op == '&':
                to1 = a[1] + b[1]
                to0 = min(a[0], b[0])
                if a[0] == b[0]: to0 += 1
                return (to0, to1)
            else:
                to0 = a[0] + b[0]
                to1 = min(a[1], b[1])
                if a[1] == b[1]: to1 += 1
                return (to0, to1)
        for c in expr:
            if c == '0': stk.append((0,1))
            elif c == '1': stk.append((1,0))
            elif c == '(': ops.append(c)
            elif c == ')':
                while ops[-1] != '(': 
                    b = stk.pop(); a = stk.pop(); op = ops.pop()
                    stk.append(merge(a, b, op))
                ops.pop()
            elif c in '&|':
                while ops and ops[-1] != '(': 
                    b = stk.pop(); a = stk.pop(); op = ops.pop()
                    stk.append(merge(a, b, op))
                ops.append(c)
        while ops:
            b = stk.pop(); a = stk.pop(); op = ops.pop()
            stk.append(merge(a, b, op))
        res = stk[-1]
        return max(res)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

impl Solution {
    pub fn min_operations_to_flip(expr: String) -> i32 {
        let mut stk = vec![];
        let mut ops = vec![];
        fn merge(a: (i32,i32), b: (i32,i32), op: char) -> (i32,i32) {
            if op == '&' {
                let to1 = a.1 + b.1;
                let mut to0 = a.0.min(b.0);
                if a.0 == b.0 { to0 += 1; }
                (to0, to1)
            } else {
                let to0 = a.0 + b.0;
                let mut to1 = a.1.min(b.1);
                if a.1 == b.1 { to1 += 1; }
                (to0, to1)
            }
        }
        for c in expr.chars() {
            match c {
                '0' => stk.push((0,1)),
                '1' => stk.push((1,0)),
                '(' => ops.push(c),
                ')' => {
                    while *ops.last().unwrap() != '(' {
                        let b = stk.pop().unwrap();
                        let a = stk.pop().unwrap();
                        let op = ops.pop().unwrap();
                        stk.push(merge(a, b, op));
                    }
                    ops.pop();
                },
                '&' | '|' => {
                    while !ops.is_empty() && *ops.last().unwrap() != '(' {
                        let b = stk.pop().unwrap();
                        let a = stk.pop().unwrap();
                        let op = ops.pop().unwrap();
                        stk.push(merge(a, b, op));
                    }
                    ops.push(c);
                },
                _ => {}
            }
        }
        while !ops.is_empty() {
            let b = stk.pop().unwrap();
            let a = stk.pop().unwrap();
            let op = ops.pop().unwrap();
            stk.push(merge(a, b, op));
        }
        let res = stk.pop().unwrap();
        res.0.max(res.1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
    minOperationsToFlip(expr: string): number {
        const stk: [number, number][] = [];
        const ops: string[] = [];
        function merge(a: [number, number], b: [number, number], op: string): [number, number] {
            if (op === '&') {
                const to1 = a[1] + b[1];
                let to0 = Math.min(a[0], b[0]);
                if (a[0] === b[0]) to0++;
                return [to0, to1];
            } else {
                const to0 = a[0] + b[0];
                let to1 = Math.min(a[1], b[1]);
                if (a[1] === b[1]) to1++;
                return [to0, to1];
            }
        }
        for (const c of expr) {
            if (c === '0') stk.push([0,1]);
            else if (c === '1') stk.push([1,0]);
            else if (c === '(') ops.push(c);
            else if (c === ')') {
                while (ops[ops.length-1] !== '(') {
                    const b = stk.pop()!;
                    const a = stk.pop()!;
                    const op = ops.pop()!;
                    stk.push(merge(a, b, op));
                }
                ops.pop();
            } else if (c === '&' || c === '|') {
                while (ops.length && ops[ops.length-1] !== '(') {
                    const b = stk.pop()!;
                    const a = stk.pop()!;
                    const op = ops.pop()!;
                    stk.push(merge(a, b, op));
                }
                ops.push(c);
            }
        }
        while (ops.length) {
            const b = stk.pop()!;
            const a = stk.pop()!;
            const op = ops.pop()!;
            stk.push(merge(a, b, op));
        }
        const res = stk[stk.length-1];
        return Math.max(res[0], res[1]);
    }
}

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the expression, as each character is processed once.
  • 🧺 Space complexity: O(n) for the stack used in parsing.