Задача: 921. Minimum Add to Make Parentheses Valid4
Сложность: medium

Строка со скобками допустима тогда и только тогда, когда: это пустая строка, ее можно записать как AB (A, совмещенное с B), где A и B - допустимые строки, или ее можно записать как (A), где A - допустимая строка. Вам дана строка s со скобками. За один ход вы можете вставить скобку в любую позицию строки. Например, если s = "()))", вы можете вставить открывающую скобку в виде "(()))" или закрывающую скобку в виде "())))". Верните минимальное количество ходов, необходимое для того, чтобы сделать s допустимой.

Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

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

1⃣Инициализировать два счетчика open_needed и close_needed.

2⃣Пройти по строке s символ за символом:
Если текущий символ - открывающая скобка (, увеличьте open_needed.
Если текущий символ - закрывающая скобка ), проверьте:
Если open_needed больше 0, уменьшите open_needed.
Иначе увеличьте close_needed.

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

😎 Решение:

function minAddToMakeValid($s) {
    $openNeeded = 0;
    $closeNeeded = 0;
    
    for ($i = 0; $i < strlen($s); $i++) {
        if ($s[$i] == '(') {
            $openNeeded++;
        } elseif ($s[$i] == ')') {
            if ($openNeeded > 0) {
                $openNeeded--;
            } else {
                $closeNeeded++;
            }
        }
    }
    
    return $openNeeded + $closeNeeded;
}

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