Условие

Дана строка s, состоящая из скобок ( и ). Она представляет собой список примитивных скобочных строк, соединенных вместе.

Удалите самую внешнюю пару скобок из каждой примитивной скобочной строки в s и верните полученную строку.

Примеры

Input: s = "(()())(())” Output: "()()()” Explanation: Первая примитивная скобочная строка — "(()())", после удаления внешних скобок остается "()()". Вторая примитивная скобочная строка — "(())", после удаления внешних скобок остается "()". Результат: "()()()".

Input: s = "(()())(())(()(()))" Output: "()()()()(())" Explanation: Первая примитивная скобочная строка — "(()())", после удаления внешних скобок остается "()()". Вторая примитивная скобочная строка — "(())", после удаления внешних скобок остается "()". Третья примитивная скобочная строка — "(()(()))", после удаления внешних скобок остается "(())". Результат: "()()()()(())".

Input: s = "()()" Output: "" Explanation: Первая примитивная скобочная строка — "()", после удаления внешних скобок остается "". Вторая примитивная скобочная строка — "()", после удаления внешних скобок остается "". Результат: "".

Решение

fun removeOuterParentheses(s: String): String {
    val result = StringBuilder()
    var balance = 0

    for (c in s) {
        // Уменьшаем баланс перед добавлением закрывающей скобки
        if (c == ')') balance--
        
        // Добавляем символ, если он не является внешней скобкой
        if (balance > 0) result.append(c)

        // Увеличиваем баланс после добавления открывающей скобки
        if (c == '(') balance++
    }

    return result.toString()
}

Временная сложность

O(n), так как проходим по строке один раз.

Пространственная сложность

O(n), так как используем StringBuilder для хранения результата.