При работе со строками часто встречаются соседние повторяющиеся символы, которые необходимо удалить. В этой статье блога мы рассмотрим различные методы эффективного удаления всех соседних дубликатов в строке, уделяя особое внимание проблеме «Удалить все соседние дубликаты в строке II». Мы предоставим примеры кода на Python, Java и C++ для демонстрации каждого метода.

Метод 1: подход на основе стека
Подход на основе стека — это интуитивное решение для удаления соседних дубликатов. Он включает в себя перебор строки и помещение символов в стек. Если текущий символ совпадает с вершиной стека, мы извлекаем символ из стека; в противном случае мы помещаем его в стек. Этот метод имеет временную сложность O(n) и пространственную сложность O(n).

def remove_duplicates(s: str, k: int) -> str:
    stack = []
    count = []

    for char in s:
        if not stack or stack[-1] != char:
            stack.append(char)
            count.append(1)
        else:
            count[-1] += 1
            if count[-1] == k:
                stack.pop()
                count.pop()

    return ''.join(stack)

Метод 2: подход с двумя указателями
Подход с двумя указателями устраняет необходимость в стеке и снижает сложность пространства до O(1). Мы поддерживаем два указателя: один для отслеживания текущего символа, а другой для отслеживания последней позиции вставки. Если текущий символ совпадает с символом в последней позиции вставки, мы проверяем, достигло ли счетчик k. Если это так, мы перемещаем позицию вставки назад на k и продолжаем. Этот метод также имеет временную сложность O(n).

public String removeDuplicates(String s, int k) {
    char[] stack = s.toCharArray();
    int[] count = new int[stack.length];
    int i = 0;

    for (int j = 0; j < stack.length; j++, i++) {
        stack[i] = stack[j];
        count[i] = (i > 0 && stack[i - 1] == stack[j]) ? count[i - 1] + 1 : 1;

        if (count[i] == k)
            i -= k;
    }

    return new String(stack, 0, i);
}

Метод 3: оптимизированный подход с двумя указателями
Мы можем дополнительно оптимизировать подход с двумя указателями, избегая избыточного копирования символов. Вместо изменения входной строки или создания новой строки мы можем имитировать удаление, отмечая символы, которые необходимо удалить. Этот метод также имеет временную сложность O(n) и пространственную сложность O(1).

string removeDuplicates(string s, int k) {
    int n = s.length();
    vector<int> count(n, 1);
    int i = 0;

    for (int j = 1; j < n; j++) {
        s[i] = s[j];
        count[i] = (i > 0 && s[i - 1] == s[j]) ? count[i - 1] + 1 : 1;

        if (count[i] == k)
            i -= k;

        i = max(i, 0);
    }

    return s.substr(0, i);
}

В этой статье мы рассмотрели три эффективных метода удаления всех соседних дубликатов в строке, а именно подход на основе стека, подход с двумя указателями и оптимизированный подход с двумя указателями. Каждый метод обеспечивает свой компромисс между сложностью времени и пространства. Понимая эти алгоритмы и их реализацию кода на Python, Java и C++, вы сможете выбрать наиболее подходящий метод для ваших конкретных требований.