Программа Java для рекурсивного удаления всех смежных дубликатов

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

Примеры :

Input: azxxzy 
Output: ay 
First “azxxzy” is reduced to “azzy”. 
The string “azzy” contains duplicates, 
so it is further reduced to “ay”.

Input: geeksforgeeg 
Output: gksfor 
First “geeksforgeeg” is reduced to 
“gksforgg”. The string “gksforgg” 
contains duplicates, so it is further 
reduced to “gksfor”.

Input: caaabbbaacdddd 
Output: Empty String

Input: acaaabbbacdddd 
Output: acac 

Для удаления дубликатов за время O(N) можно использовать следующий подход :

• Начните с самого левого символа и удалите дубликаты в левом углу, если они есть.
• Теперь первый символ должен отличаться от соседнего. Recur для строки длины n-1 (строка без первого символа).
• Пусть строка, полученная после сокращения правой подстроки длины n-1, будет rem_str . Возможны три случая
  1. Если первый символ rem_str совпадает с первым символом исходной строки, удалите первый символ из rem_str .
  2. Если оставшаяся строка становится пустой, а последний удаленный символ совпадает с первым символом исходной строки. Вернуть пустую строку.
  3. В противном случае добавьте первый символ исходной строки в начало rem_str .
• Вернуть rem_str .

На изображении ниже показан пробный запуск описанного выше подхода:

Ниже приведена реализация вышеуказанного подхода:

Выход:

gksfor
ay
g
a
qrq
acac
a

Временная сложность: временная сложность решения может быть записана как T (n) = T (nk) + O (k), где n — длина входной строки, а k — количество первых одинаковых символов. Решение повторения O (n)

Спасибо Prachi Bodke за предложение этой проблемы и первоначальное решение.

Другой подход:
Идея здесь состоит в том, чтобы проверить, имеет ли строка remStr повторяющийся символ, который соответствует последнему символу родительской строки. Если это происходит, то мы должны продолжать удалять этот символ перед конкатенацией строки s и строки remStr.

Ниже приведена реализация вышеуказанного подхода:

Выход:

mpie
lop

Временная сложность: O(n)

Пожалуйста, обратитесь к полной статье о рекурсивном удалении всех смежных дубликатов для получения более подробной информации!