https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses

When you see in problem formulation, that it is something about valid parantheses, you should immedietly thing about stack, because the very classical problems in this topic uses stack.

Let us traverse our string from left to right and make sure, that we do not have any problems with balance:

  1. If symbol is (, then we increase balance by 1 and add this symbol to ans.
  2. If symbol is ), then we can add this symbol only if balance is positive: if it is 0, then we can not recover our string if we continue.
  3. If symbol not ( and not ), we add it to ans.

However, it is not enough to do only one traverse: so far when we finished, we can say that:

  1. Balance is never negative
  2. But balance in the end should be equal to 0.

These 2 conditions and sufficient and enough to have valid parentheses and at the moment only the fist one is fulfilled. What we can do now is to traverse string from the end and keep removing symbols until balance becomes equal to 0. Or we can use our clean function and apply it to reversed string.

Complexity: time complexity is O(n), we traverse our string twice. Space complexity is also O(n).

class Solution:
    def minRemoveToMakeValid(self, s):
        def clean(s, op, cl):
            balance, ans = 0, ""
            for i in s:
                if i == op:
                    balance += 1
                    ans += i
                elif i == cl and balance > 0:
                    balance -= 1
                    ans += i
                elif i not in "()":
                    ans += i              
            return ans
        
        return clean(clean(s, "(", ")")[::-1], ")", "(")[::-1]

If you like the solution, you can upvote it on leetcode discussion section: Problem 1249