1249

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:

        st = []
        remove = set()
        res = []

        for i, c in enumerate(s):
            if c == '(':
                st.append(i)
            elif c == ')' and st:
                st.pop()
            elif c == ')':
                remove.add(i)

        while st:
            remove.add(st.pop())

        for i, c in enumerate(s):
            if i not in remove:
                res.append(c)

        return ''.join(res)