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

        #TC: O(n)
        #SC: O(n)

        stack = []
        left = 0
        for ele in s:
            if ele == ')':
                if left == 0:
                    stack.append('')
                else:
                    left -= 1
                    stack.append(ele)
            elif ele == '(':
                left += 1
                stack.append(ele)
            else:
                stack.append(ele)

        stack.reverse()

        right = 0
        for idx, ele in enumerate(stack):
            if ele == '(':
                if right == 0:
                    stack[idx] = ''
                else:
                    right -= 1
            elif ele == ')':
                right += 1

        return  ''.join(stack)[::-1]