Настоящее название этой задачи — «Лексикографически наибольшая подпоследовательность-палиндром» — слишком длинное, чтобы уместиться в заголовке страницы.

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

Непустую строку s[p₁p₂... p_k] = s_p1s_p2... s_pk (1  ≤  p₁ < p₂ < ... < p_k  ≤  |s|) будем называть подпоследовательностью строки s = s₁s₂... s_|s|, где |s| — длина строки s. Например, строки «abcb», «b» и «abacaba» являются подпоследовательностями строки «abacaba».

Строка x = x₁x₂... x_|x| лексикографически больше строки y = y₁y₂... y_|y|, если либо |x| > |y| и x₁ = y₁, x₂ = y₂, ..., x_|y| = y_|y|, либо существует такое число r (r < |x|, r < |y|), что x₁ = y₁, x₂ = y₂, ..., x_r = y_r и x_{r  +  1} > y_{r  +  1}. Символы в строках сравниваются как их ASCII-коды. Например, строка «ranger» лексикографически больше строки «racecar», а строка «poster» лексикографически больше строки «post».

Строка s = s₁s₂... s_|s| называется палиндромом, если она в точности совпадает со строкой rev(s) = s_|s|s_|s| - 1... s₁. Иными словами, строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строками-палиндромами являются «racecar», «refer» и «z».