class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        res = []
        cnt = 0  # extra ( parentheses
        for c in s:
            if c == "(":
                res.append(c)
                cnt += 1
            elif c == ")" and cnt > 0:
                res.append(c)
                cnt -= 1
            elif c != ")":
                res.append(c)

        filtered = []
        for c in reversed(res):
            if c == "(" and cnt > 0:
                cnt -= 1
            else:
                filtered.append(c)
        return "".join(reversed(filtered))

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        arr = list(s)
        cnt = 0  # extra ( parentheses
        for i, c in enumerate(s):
            if c == "(":
                cnt += 1
            elif c == ")" and cnt > 0:
                cnt -= 1
            elif c == ")":
                arr[i] = ''

        res = []
        for c in reversed(arr):
            if c == '(' and cnt > 0:
                cnt -= 1
            else:
                res.append(c)

        return ''.join(reversed(res))

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        s = list(s)
        stack = []
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            elif c == ')':
                if stack:
                    stack.pop()
                else:
                    s[i] = ''

        while stack:
            s[stack.pop()] = ''
        return ''.join(s)

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        openCnt = closeCnt = 0
        for c in s:
            closeCnt += c == ')'

        res = []
        for c in s:
            if c == '(':
                if openCnt == closeCnt:
                    continue
                openCnt += 1
            elif c == ')':
                closeCnt -= 1
                if openCnt == 0:
                    continue
                openCnt -= 1
            res.append(c)

        return ''.join(res)