Условие

Дана строка s, состоящая только из строчных букв. Удаляйте из неё пары соседних одинаковых символов, пока это возможно. Верните получившуюся строку.

Примеры

Input: s = "abbaca” Output: "ca” Explanation: Например, в "abbaca" можно удалить "bb", так как буквы одинаковые и стоят рядом. После этого строка превращается в "aaca", где можно удалить "aa". Итоговая строка — "ca".

Input: s = "azxxzy” Output: "ay”

Решение

fun removeDuplicates(s: String): String {
    val stack = ArrayDeque<Char>()

    for (c in s) {
        if (stack.isNotEmpty() && stack.last() == c) {
            stack.removeLast() // Удаляем пару одинаковых символов
        } else {
            stack.addLast(c) // Добавляем символ в стек
        }
    }

    return stack.joinToString("") // Собираем строку из стека
}

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

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

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

O(n), в худшем случае, если нет удаляемых пар.