Задача: 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⃣Создайте новую строку, удалив все помеченные скобки.

😎 Решение:

class Solution {
    function minRemoveToMakeValid($s) {
        $stack = [];
        $s = str_split($s);
        for ($i = 0; $i < count($s); $i++) {
            if ($s[$i] == '(') {
                array_push($stack, $i);
            } elseif ($s[$i] == ')') {
                if (!empty($stack)) {
                    array_pop($stack);
                } else {
                    $s[$i] = '';
                }
            }
        }
        while (!empty($stack)) {
            $s[array_pop($stack)] = '';
        }
        return implode('', $s);
    }
}

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