这个问题的实际名称“字典顺序最大回文子序列”太长,无法放入页面标题中。
给出的字符串 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”。
输入
唯一的输入行包含仅由小写英文字母组成的非空字符串 s。其长度不超过10。
输出
打印字符串 s 的字典顺序最大的回文子序列。
示例
输入 #1
radar
输出 #1
rr
输入 #2
bowwowwow
输出 #2
wwwww
输入 #3
codeforces
输出 #3
s
输入#4
mississipp
输出#4
ssss
注意
在字符串“radar”的所有不同子序列中,以下是回文:“a”、“d”、“r”、“aa”、“rr”、“ada”、“rar”、“rdr”、“raar”和“radar”。其中按字典顺序最大的是“rr”。