Удалить минимальное число скобок, чтобы сделать скобочное выражение правильным

Задача.

Дана строка состоящая из круглых скобок '(' и ')', а также английских букв в нижнем регистре. Нужно удалить минимальное число скобок, чтобы сделать скобочное выражение правильным.

Ссылка на leetcode: https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/

Примеры:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

Input: s = "a)b(c)d"
Output: "ab(c)d"

Input: s = "))(("
Output: ""

Решение.

Можно воспользоваться решением похожей задачи: проверить правильность скобочного выражения.
В основе этого решения лежит использование стека. Мы циклом проходим по строке. Если это открывающаяся скобка - помещаем ее в стек. Если закрывающаяся, то делаем проверку того, что лежит в голове стека. Если это соответствующая открывающаяся скобка, то все в порядке, достаем ее из стека. Если стек пуст или там не соответствующая открывающаяся скобка, то выражение не валидно и скобка не скомпенсирована. Когда закончим цикл по строке, проверим стек пуст или нет. Если нет, это значит, что есть нескомпенсированные скобки, а следовательно скобочное выражение не валидно.
В нашем случае у нас только один вид скобок, поэтому этот код упрощается до:

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            stack.push(c);
        } else if (c == ')') {
            if (stack.isEmpty()) {
                return false;
            }
            stack.pop();
        }
    }
    return stack.isEmpty();    
}

Это решение можно расширить, чтобы получить решение исходной задачи. В тот момент, когда мы встречаем нескомпенсированную скобку, мы можем запоминать ее индекс, чтобы позже ее удалить. Для этого в стеке будем хранить не саму скобку, а ее индекс. Более того будем хранить список всех скобок для удаления в HashSet. В конце, если стек не пуст - то он будет содержать индексы нескомпенсированных скобок, которые нужно удалить. Их мы переместим в наш HashSet. Далее мы снова циклом пройдем по нашей строке, и на ее основе будем создавать новую строку, которая не будет содержать скобок, которые нужно удалить. Это нужно в силу того, что строки в Java immutable. Строку нельзя изменить, можно создать новую.
Итоговый код:

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