334. Minimum Remove to Make Valid Parentheses

Scan once. Push each '(' index onto a stack; on a ')', pop a match or mark this ')' for removal. Any '(' left on the stack at the end is also unmatched.

Two kinds of unmatched

Walk the string keeping a stack of indices of unmatched (:

• On (: push its index.
• On ): if the stack is non-empty, pop (matched); otherwise mark this ) for removal.

After the pass, every index still on the stack is an unmatched ( — mark those too. Build the result skipping all marked positions.

for i, c in enumerate(s):
    if c == '(': stack.push(i)
    elif c == ')': stack.pop() if stack else remove[i]
remove all indices left on stack

Worked example

"lee(t(c)o)de)" → the trailing unmatched ) is removed → "lee(t(c)o)de".

Complexity

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

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public String minRemoveToMakeValid(String s) {
        char[] arr = s.toCharArray();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '(') {
                stack.push(i);
            } else if (arr[i] == ')') {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    arr[i] = 0;  // mark for removal
                }
            }
        }
        while (!stack.isEmpty()) {
            arr[stack.pop()] = 0;
        }
        StringBuilder sb = new StringBuilder();
        for (char c : arr) {
            if (c != 0) sb.append(c);
        }
        return sb.toString();
    }
}