Задача 4D. Извлечение ключа ≡

Условие

Алиса хочет передать Бобу по открытому каналу связи секретный ключ для дальнейшего шифрования сообщений. В силу ряда обстоятельств у неe не получится воспользоваться современными методами кодирования с открытым ключом. Поэтому ранее, при личной встрече, Алиса и Боб договорились, что в таком случае будут пользоваться методом «иголка в стоге сена» или стеганографией. Алиса передаст Бобу строку из малых букв латиницы, в которую как подпоследовательность будет «вплетена» строка, являющаяся ключом.

Строка s₂ является подпоследовательностью строки s₁, если еe можно получить путeм удаления некоторых символов из s₁, не меняя порядок оставшихся символов.

Например если s₁ это abracadabra, то еe подпоследовательностями являются babr, arcada, aacaa и r. В то же время, такие строки как bob, bard и d_c не являются подпоследовательностями строки s₁.

Ключ, который хочет передать Алиса, состоит из малых букв латиницы и обладает следующим свойством: любые два рядом стоящие в нeм символа находятся рядом и в алфавите. То есть следующий символ ключа по отношению к предыдущему является либо следующей, либо предыдущей буквой латиницы. Назовeм такие строки «правильными». Например, правильными являются строки cdef edef gh или abababab, а вот строки abba или cede не являются правильными.

Алиса очень постаралась и «зашила» ключ в строку так, что Боб серьезно задумался. Он знает, что нужно выбрать из полученной строки самую длинную правильную подпоследовательность, и если таких несколько, взять самую большую по лексикографическому (алфавитному) порядку. Но «знать» и «уметь делать» - очень разные вещи. Нужно помочь Бобу извлечь искомый ключ.

Пояснения к примеру

В присланной Алисой строке bdaedbceab содержатся следующие правильные подпоследовательности длины 5: babab, babcb и dedcb. Последняя, так как она лексикографически самая большая, и будет ответом.

Формат входных данных

В первой строке содержится число n - длина строки, которую прислала Алиса.

1 ≤ n ≤ 3·10⁵.

Во второй строке приведена сама строка, которую прислала Алиса. Она состоит из малых букв латиницы.

Формат выходных данных

В ответ вывести одну строку - «спрятанный» в исходной строке по указанным выше правилам ключ.

Примеры тестов

10
bdaedbceab

dedcb

Разбор

Для решения задачи будем использовать метод динамического программирования. В первом приближении решение выглядит так: пробежимся по символам исходной строки и для текущей буквы (именно буквы, а не позиции этой буквы в строке), запомним максимальную длину правильной подпоследовательности для уже просмотренного префикса, которая заканчивается в этой букве (обозначим этот массив dp). Для этого нужно посмотреть уже полученную длину в букве, являющейся предыдущей в алфавите для текущей и в следующей в алфавите для текущей. Ключевой момент: если длина больше в предыдущей, то запомним для текущей эту длину плюс 1, иначе, если равна или больше в следующей - запомним именно этот показатель плюс 1 в текущей букве. Таким образом, мы при равной длине при восстановлении ответа уйдем в большую в алфавите букву, что и гарантирует правильный ответ в случае, когда длиннейших вариантов ответа несколько. Не забудем, что у букв «a» и «z» есть только один сосед в алфавите.

При построении массива dp параллельно будем поддерживать массив par - родителей для текущей позиции (уже именно позиции), указывающий на какую позицию в строке нужно вернуться из текущей, чтобы получить самую лучшую правильную подстроку, которая заканчивается в данной позиции (стандартное восстановление пути). Кроме того, для каждой буквы алфавита поддерживаем массив pos, в котором хранится индекс последнего вхождения этой буквы (для каждой буквы выгодно брать самое последнее еe вхождение в исходную строку, находящееся левее текущего).