[Python] Two-pass O(n) solution, explained
When you see in problem formulation, that it is something about valid parantheses, you should immedietly thing about stack, because the very classical problems 
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.\n\nLet us traverse our string from left to right and make sure, that we do not have any problems with balance:\n1. If symbol is `(`, then we increase balance by `1` and add this symbol to `ans`.\n2. 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.\n3. If symbol not `(` and not `)`, we add it to `ans`.\n\nHowever, it is not enough to do only one traverse: so far when we finished, we can say that:\n1. Balance is never negative\n2. But balance in the end should be equal to `0`.\n\nThese `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.\n\n**Complexity**: time complexity is `O(n)`, we traverse our string twice. Space complexity is also `O(n)`.\n\n```\nclass Solution:\n    def minRemoveToMakeValid(self, s):\n        def clean(s, op, cl):\n            balance, ans = 0, ""\n            for i in s:\n                if i == op:\n                    balance += 1\n                    ans += i\n                elif i == cl and balance > 0:\n                    balance -= 1\n                    ans += i\n                elif i not in "()":\n                    ans += i              \n            return ans\n        \n        return clean(clean(s, "(", ")")[::-1], ")", "(")[::-1]\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
['Stack']