Python | Fast & Easy | Beats 98%
Time complexity: O(n)\n\nBrief description:\n\nThere is one loop of searching parentheses in the string.  It\'s important to use a stack to store the positions 
Time complexity: O(n)\n\nBrief description:\n\nThere is one loop of searching parentheses in the string.  It\'s important to use a stack to store the positions of open parentheses, because during iteration open parentheses are added and popped from the top of this data collection . In python the best implementation of the stack is using a list.\n\nThere are 2 reasons to remove parentheses:\n1) If there is a valid parentheses string before a close parenthesis, remove this parenthesis.  This removal is done during the loop, so the string was converted to a list at the beginning.\n2) If there are extra open parentheses (the stack is not empty), these parantheses should be deleted.\n\n\nSolution:\n```\nclass Solution:\n    def minRemoveToMakeValid(self, s: str) -> str:\n        stack = []\n        s = list(s)\n        for i in range(len(s)):\n            if s[i] == "(": stack.append(i)\n            elif s[i] == ")":\n                if stack: stack.pop()\n                else: s[i] = ""\n        for i in stack:\n            s[i] = ""\n        return "".join(s)\n```
['Stack', 'Python', 'Python3']