minRemoveToMakeValid

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()) {
                    remove.add(i);
                } else {
                    stack.pop();
                }
            }
        }

        while (!stack.isEmpty()) {
            remove.add(stack.pop());
        }

        String result = "";
        for (int i = 0; i < s.length(); i++) {
            if (!remove.contains(i)) {
                result += s.charAt(i);
            }
        }

        return result;
    }
}