Самая короткая строка после удаления всех пар одинаковых соседних символов

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

Примеры:

Input: S = “aaabccddd”
Output: abd
Explanation: Following sequence of removal of pairs of adjacent characters minimizes the length of the string: 
aaabccddd → abccddd → abddd → abd.

Input: S = aa
Output: Empty String
Explanation: Following sequence of removal of pairs of adjacent characters minimizes the length of the string: 
aa → “”.

Подход: Основная идея решения данной проблемы состоит в том, чтобы рекурсивно удалить все пары соседних символов, которые равны, один за другим. Выполните шаги, чтобы решить данную проблему:

• Инициализируйте пустую строку, скажем, ans , чтобы сохранить строку минимальной длины после удаления всех пар одинаковых соседних символов.
• Инициализируйте строку, скажем, pre , чтобы сохранить обновленную строку после каждого удаления одинаковых соседних символов.
• Теперь итерируйте до тех пор, пока строки ans и pre не станут неравными, и выполните следующие шаги:
  • Обновите значение строки an , удалив первый соседний такой же символ с помощью функции removeAdjacent() .
  • Если значение строки an совпадает со строкой pre , выходим из цикла. В противном случае обновите значение строки pre как строку an .
• После выполнения вышеуказанных шагов выведите строку ans в качестве результирующей строки.

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

Временная сложность: O(N ² )
Вспомогательное пространство: O(N)