Задача: 921. Minimum Add to Make Parentheses Valid
Сложность: 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, чтобы получить минимальное количество вставок.

😎 Решение:

var minAddToMakeValid = function(s) {
    let openNeeded = 0, closeNeeded = 0;
    
    for (const char of s) {
        if (char === '(') {
            openNeeded++;
        } else if (char === ')') {
            if (openNeeded > 0) {
                openNeeded--;
            } else {
                closeNeeded++;
            }
        }
    }
    
    return openNeeded + closeNeeded;
};

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