Minimum Remove To Make Parentheses Valid#

 1balance("()") -> "()"
 2balance("a(b)c)") -> "a(b)c"
 3balance(")(") -> ""
 4balance("(((((") -> ""
 5balance("(()()(") -> "()()"
 6balance(")(())(") -> "(())"
 7balance(")())(()()(") -> "()()()"
 8
 9balance(")a(") -> "a"
10balance(")a()") -> "a()"
11balance("()a(") -> "()a"

 1from typing import List
 2
 3
 4def balance_parentheses(s: str) -> str:
 5    """
 6    Remove the minimum number of parentheses to make the string valid.
 7
 8    Approach:
 9    - Scan once:
10      - push indices of '(' onto stack
11      - when seeing ')', pop if possible; otherwise mark this ')' as invalid
12    - Any remaining '(' in stack are invalid too
13    - Build result skipping all invalid indices
14
15    Time:  O(n)
16    Space: O(n)
17    """
18    if not s:
19        return ""
20
21    stack: List[int] = []
22    invalid = set()
23
24    for i, ch in enumerate(s):
25        if ch == '(':
26            stack.append(i)
27        elif ch == ')':
28            if stack:
29                stack.pop()
30            else:
31                invalid.add(i)
32
33    # Unmatched '(' are invalid
34    invalid.update(stack)
35
36    # Rebuild string
37    out = []
38    for i, ch in enumerate(s):
39        if i not in invalid:
40            out.append(ch)
41    return "".join(out)