Palindrome

题意翻译

题面: 给你一个字符串 $s$,确认它是否包含有长度为 $100$ 的回文子序列,如果有,输出其中一个;如果没有,输出它所包含的最长回文子序列。 输入: 一个长度为 $n$($1 \le n \le 5 \times {10}^4$)的字符串 $s$。 输出: 如果它有长度为 $100$ 的回文子序列,输出其中一种;否则输出其包含的最长回文子序列。 提示: 一个字符串的子序列可以通过删除原字符串中**任意字符**而**不改变**原本字符顺序产生。 感谢 @\_\_\_\_233\_\_\_\_ 提供的翻译

题目描述

Given a string $ s $ , determine if it contains any palindrome of length exactly $ 100 $ as a subsequence. If it has any, print any one of them. If it doesn't have any, print a palindrome that is a subsequence of $ s $ and is as long as possible.

输入输出格式

输入格式


The only line of the input contains one string $ s $ of length $ n $ ( $ 1<=n<=5·10^{4} $ ) containing only lowercase English letters.

输出格式


If $ s $ contains a palindrome of length exactly $ 100 $ as a subsequence, print any palindrome of length $ 100 $ which is a subsequence of $ s $ . If $ s $ doesn't contain any palindromes of length exactly $ 100 $ , print a palindrome that is a subsequence of $ s $ and is as long as possible. If there exists multiple answers, you are allowed to print any of them.

输入输出样例

输入样例 #1

bbbabcbbb

输出样例 #1

bbbcbbb

输入样例 #2

rquwmzexectvnbanemsmdufrg

输出样例 #2

rumenanemur

说明

A subsequence of a string is a string that can be derived from it by deleting some characters without changing the order of the remaining characters. A palindrome is a string that reads the same forward or backward.