Problem statement

https://binarysearch.com/problems/Removing-Parentheses/

Solution

We need to check balance when we go from one and and from another.

Complexity

It is O(n) for time and O(1) for space. Similar to Leetcode 1249. Minimum Remove to Make Valid Parentheses.

Code

class Solution:
    def solve(self, s):
        bal = 0
        ans1 = 0
        for i in s:
            bal += 1 if i == "(" else -1
            if bal < 0: ans1 = max(ans1, -bal)

        bal = 0
        ans2 = 0
        for i in s[::-1]:
            bal += 1 if i == ")" else -1
            if bal < 0: ans2 = max(ans2, -bal)

        return ans1 + ans2