Python in 12 lines to solve the classic parentheses problem
1st approach\n\nHere was my first approach using the way I solved #921 \nNot the best but easy to come up with if you solved similar problem e.g. #921 #20  \n\n
#### 1st approach\n\nHere was my first approach using the way I solved [#921](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid) \nNot the best but easy to come up with if you solved similar problem e.g. [#921](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid) [#20](https://leetcode.com/problems/valid-parentheses)  \n\n```py\n"""\n    1st: stack + hashtable\n    - similar to lc921 but save the indices of the redundant opens & closes\n    - construct the result by removing the characters at redundant indices\n    - 12 lines\n    \n    Time    O(3N)\n    Space   O(N)\n    164 ms, faster than 79.33%\n"""\nclass Solution(object):\n    def minRemoveToMakeValid(self, s):\n        opens, closes = [], []\n        for i in range(len(s)):\n            c = s[i]\n            if c == \'(\':\n                opens.append(i)\n            elif c == \')\':\n                if len(opens) == 0:\n                    closes.append(i)\n                else:\n                    opens.pop()\n        hs = set(opens+closes)\n        return \'\'.join(s[i] for i in range(len(s)) if i not in hs)\n```\n\n#### 2nd approach\n\nIf you don\'t like hashtable, we can just construct an array to save the redundant parentheses and solve the problem in the same way\n\n```py\n"""\n    2nd: similar logic without using a hashtable\n\t- 17 lines\n\n    Time    O(3N)\n    Space   O(N)\n    244 ms, faster than 45.31%\n"""\n\n\nclass Solution(object):\n    def minRemoveToMakeValid(self, s):\n        res, opens = [], []\n        for i in range(len(s)):\n            c = s[i]\n            if c == \'(\':\n                opens.append(i)\n                res += c\n            elif c == \')\':\n                if len(opens) == 0:\n                    res += \'*\'\n                else:\n                    opens.pop()\n                    res += c\n            else:\n                res += c\n        for x in opens:\n            res[x] = \'*\'\n        return \'\'.join(c for c in res if c != \'*\')\n```
[]