Задача: 1249. Minimum Remove to Make Valid Parentheses
Сложность: medium

Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.

Пример:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

👨‍💻 Алгоритм:

1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления.

2⃣После первого прохода, все оставшиеся в стеке открывающие скобки пометьте для удаления.

3⃣Создайте новую строку, удалив все помеченные скобки.

😎 Решение:
public class Solution {
public String minRemoveToMakeValid(String s) {
StringBuilder sb = new StringBuilder(s);
Stack stack = new Stack();
for (int i = 0; i < sb.length(); i++) {
if (sb.charAt(i) == '(') {
stack.push(i);
} else if (sb.charAt(i) == ')') {
if (!stack.isEmpty()) {
stack.pop();
} else {
sb.setCharAt(i, '*');
}
}
}
while (!stack.isEmpty()) {
sb.setCharAt(stack.pop(), '*');
}
return sb.toString().replaceAll("\\*", "");
}
}

Ставь 👍 и забирай 📚 Базу знаний