Удалить соседние дубликаты в строке

Постановка задачи

s = "abbaca"

"ca"

s = "azxxzy"

"ay"

Решение

Если удалить пару символов в середине строки, рядом могут оказаться символы, которые раньше не были соседями. Поэтому простого прохода с удалением из строки недостаточно: после каждого удаления пришлось бы возвращаться назад.

Стек позволяет легко решить эту проблему. Стек хранит текущую строку после всех удалений, которые уже можно было сделать.

Идея решения:

Идем по символам строки слева направо. Для каждого символа смотрим на вершину стека:

1. Если стек не пуст и верхний символ равен текущему, значит, мы нашли соседнюю пару. Удаляем верхний символ из стека и не добавляем текущий.
2. Иначе кладем текущий символ в стек.

В конце стек содержит ответ.

Рассмотрим пример s = "abbaca":

1. a - стек пуст, кладем.

2. b - на вершине a, кладем.

3. b - на вершине тоже b, удаляем из стека.

4. a - на вершине тоже a, удаляем.

5. c - кладем.

6. a - кладем. Ответ: "ca".

Оценка сложности

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

Мы обрабатываем каждый символ один раз. Каждая операция со стеком занимает O(1), поэтому временная сложность равна O(n).

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

В худшем случае удалений не будет, и стек сохранит все символы. Пространственная сложность равна O(n).

Код решения

Приведем код решения.

func removeDuplicates(s string) string {
    stack := []byte{}
    for i := 0; i < len(s); i++ {
        ch := s[i]
        if len(stack) > 0 && stack[len(stack)-1] == ch {
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, ch)
        }
    }
    return string(stack)
}

Итоги

Задача Remove All Adjacent Duplicates In String - это простой пример стека, который хранит уже обработанную часть строки.

1. Суть алгоритма: текущий символ сравнивается только с вершиной стека. Если они равны, пара удаляется. Если нет, символ становится новым кандидатом для будущего удаления.
2. Эффективность:
   • Временная сложность: O(n), так как каждый символ добавляется и удаляется не более одного раза.
   • Пространственная сложность: O(n), если в строке нет удаляемых пар.
3. Граничные случаи:
   • Все символы удаляются: стек становится пустым, ответом будет пустая строка.
   • Удалений нет: стек постепенно накопит всю исходную строку.
4. Оптимальное решение: стек избавляет нас от повторных проходов по строке. После удаления пары предыдущий символ автоматически становится вершиной и сразу готов к сравнению со следующими символами.