Настоящее название этой задачи — «Лексикографически наибольшая подпоследовательность-палиндром» — слишком длинное, чтобы уместиться в заголовке страницы.
Дана строка s, состоящая только из строчных латинских букв. Найдите ее лексикографически наибольшую подпоследовательность, являющуюся палиндромом.
Непустую строку s[p1p2... pk] = sp1sp2... spk (1 ≤ p1 < p2 < ... < pk ≤ |s|) будем называть подпоследовательностью строки s = s1s2... s|s|, где |s| — длина строки s. Например, строки «abcb», «b» и «abacaba» являются подпоследовательностями строки «abacaba».
Строка x = x1x2... x|x| лексикографически больше строки y = y1y2... y|y|, если либо |x| > |y| и x1 = y1, x2 = y2, ..., x|y| = y|y|, либо существует такое число r (r < |x|, r < |y|), что x1 = y1, x2 = y2, ..., xr = yr и xr + 1 > yr + 1. Символы в строках сравниваются как их ASCII-коды. Например, строка «ranger» лексикографически больше строки «racecar», а строка «poster» лексикографически больше строки «post».
Строка s = s1s2... s|s| называется палиндромом, если она в точности совпадает со строкой rev(s) = s|s|s|s| - 1... s1. Иными словами, строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строками-палиндромами являются «racecar», «refer» и «z».
Примечание
Из всех различных подпоследовательностей строки «radar» палиндромами являются «a», «d», «r», «aa», «rr», «ada», «rar», «rdr», «raar» и «radar». Лексикографически наибольшей из них является «rr».