Constraints

• 1 <= len(s) <= 100000
• s consists of lowercase English letters and parentheses '(' and ')'
• Return the unique string produced by deleting all unmatched ')' (found during a left-to-right scan) and then deleting any remaining unmatched '(' (from right to left)
• Expected time complexity O(n) and space complexity O(n)

Examples

Solution

def min_remove_to_make_valid(s: str) -> str:
    stack = []  # indices of '('
    remove = set()  # indices to delete

    for i, ch in enumerate(s):
        if ch == '(':  # push index of '('
            stack.append(i)
        elif ch == ')':
            if stack:
                stack.pop()  # match with a previous '('
            else:
                remove.add(i)  # unmatched ')'

    # Remaining '(' are unmatched
    for idx in stack:
        remove.add(idx)

    if not remove:
        return s

    res = []
    for i, ch in enumerate(s):
        if i not in remove:
            res.append(ch)
    return ''.join(res)

Explanation

Time complexity: O(n). Space complexity: O(n).

Hints

1. Track indices of '(' using a stack.
2. When you see ')', if the stack is empty mark this index for removal, otherwise pop a '(' index.
3. After scanning, any indices left in the stack are unmatched '(' and should be removed.
4. Build the answer by skipping all marked indices.