Problem statement

https://binarysearch.com/problems/Toggle-Bitwise-Expression/

Solution

Equal to Leetcode 1896. Minimum Cost to Change the Final Value of Expression.

Complexity

Time complexity can be estimated as O(n), because in fact for every valid substring we have we will call it once. Space complexity is O(n) as well.

Code

class Solution:
    def minOperationsToFlip(self, E):
        def corr(s):
            stack, d = [], {}
            for i, elem in enumerate(s):
                if elem == "(":
                    stack.append(i)
                elif elem == ")":
                    last = stack.pop()
                    d[i] = last
            return d

        def dfs(beg, end):
            if beg == end: return (int(E[beg]) , 1)
            beg2 = d.get(end, end)
            if beg2 == beg: return dfs(beg + 1, end - 1)
            p1, c1 = dfs(beg, beg2 - 2)
            p2, c2 = dfs(beg2, end)
            op = E[beg2 - 1]
            
            t = {"|": lambda x, y:x|y, "&": lambda x, y:x&y}
            c3 = 1 if p1 + p2 == 1 else min(c1, c2) + (p1^(op == "&"))
            return (t[op](p1, p2), c3)
            
        d = corr(E)
        return dfs(0, len(E) - 1)[1]