python stack O(N)
\nclass Solution:\n    def minRemoveToMakeValid(self, s: str) -> str:\n        \n        stack, cur = [], \'\'\n        for c in s:\n            if c == \'(\':\
```\nclass Solution:\n    def minRemoveToMakeValid(self, s: str) -> str:\n        \n        stack, cur = [], \'\'\n        for c in s:\n            if c == \'(\':\n                stack += [cur]\n                cur = \'\'\n            elif c == \')\':\n                if stack:\n                    cur = stack.pop() + \'(\' + cur + \')\' \n            else:\n                cur += c\n        \n        while stack:\n            cur = stack.pop() + cur\n        \n        return cur\n```\n\n@licaiuu also provided a good solution, which is really easy to understand. It is simplified as following:\n```\nclass Solution:\n    def minRemoveToMakeValid(self, s: str) -> str:\n        \n        stack, res = [], [\'\'] * len(s)\n        \n        for i, x in enumerate(s):\n            \n            if x == \'(\':\n                stack += [i]\n                \n            elif x == \')\':\n                if stack:\n                    res[stack.pop()] = \'(\'\n                    res[i] = \')\'\n                    \n            else:\n                res[i] = x\n        return \'\'.join(res)\n```\n\t\t
[]