← 返回题目列表

Codeforces · 202/A

A. 最长字典序回文子序列

中文机器翻译题面 查看原题

这个问题的实际名称“字典顺序最大回文子序列”太长,无法放入页面标题中。

给出的字符串 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”。