1249. Minimum Remove to Make Valid Parentheses

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

Python

Time: O(2N)
Space: O(k) # k stands for removal item's number

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = []
        chars = list(s)

        removal = set()

        for index, char in enumerate(chars):
            if char == '(':
                stack.append(index)
            elif char == ')':
                if not stack:
                    removal.add(index)
                else:
                    stack.pop()

        removal ^= set(stack)
        result = []
        for index, char in enumerate(chars):
            if index in removal:
                continue
            result.append(char)

        return ''.join(result)

Python​

Python