Минимальное количество требуемых удалений, при котором ни одна подпоследовательность длины 2 не встречается более одного раза.

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

Примеры:

Input: S = “abcaadbcd”
Output: abcd
Explanation: Removing the characters at indices {2, 3, 4, 5, 6, 7} modifies the string to “abcd”, that contains every subsequence of length 2 exactly once.

Input: S = “cadbcc”
Output: cadbc

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

• Инициализируйте пустую строку, скажем, ans , чтобы сохранить результирующую окончательную строку.
• Инициализируйте логический массив C[] размером 26 , чтобы проверить, присутствует ли символ в конечной строке или нет.
• Инициализируйте переменную, скажем, pos как 0 , чтобы сохранить индекс последнего символа, добавленного в строку, и .
• Пройдите по заданной строке S и, если текущий символ отсутствует в ans , добавьте его в ans , отметьте его как посещенный в массиве C[] и обновите значение pos до i .
• Перебрать диапазон [pos + 1, N – 1], используя переменную i , и если S[i] равно S[0] , добавить ее к последней строке и выйти из цикла.
• После выполнения вышеуказанных шагов выведите строку an в качестве результата.

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

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