Minimum Remove to Make Valid Parentheses

Given a string s of (, ), and lowercase letters, remove the minimum number of invalid parentheses to make the string valid. Return the result.

Example 1

Input: "lee(t(c)o)de)" → Output: "lee(t(c)o)de"

Example 2

Input: "a)b(c)d" → Output: "ab(c)d"

Solution Approach

Use a stack to track indices of unmatched ( characters. Also track indices of unmatched ). Then remove all characters at those indices.

Use a stack to store indices of unmatched (.
Scan left to right: push index for (, for ) either pop from stack (match) or mark ) index for removal.
After scan, all indices still in stack are unmatched (: mark for removal.
Build result skipping all marked indices.

Java

import java.util.*;

class Solution {
    public String minRemoveToMakeValid(String s) {
        Set<Integer> remove = new HashSet<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') stack.push(i);
            else if (c == ')') {
                if (!stack.isEmpty()) stack.pop();
                else remove.add(i);
            }
        }
        while (!stack.isEmpty()) remove.add(stack.pop());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++)
            if (!remove.contains(i)) sb.append(s.charAt(i));
        return sb.toString();
    }
}

Time Complexity: O(N)
Space Complexity: O(N)