LLPS


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal

Se le dan cadenas que consisten solo en letras minúsculas en inglés. Encuentre su subsecuencia palindrómica lexicográficamente más grande (Lexicographically Largest Palindromic Subsequence).

Llamaremos a una cadena no vacía s[p1p2...pk] = sp1sp2...spk (1p1p2...pk |s|) una subsecuencia de la cadena s=s1s2...s|s|, donde |s| es la longitud de la cadena s. Por ejemplo, las cadenas abcb, b y abacaba son subsecuencias de la cadena abacaba.

La cadena x=x1x2...x|x| es lexicográficamente más grande que la cadena y=y1y2...y|y| si |x| > |y| y x1=y1, x2=y2, ..., x|y|=y|y|, o existe tal número r (r<|x|, r<|y|) que x1=y1, x2=y2, ..., xr=yr y xr+1>yr+1. Los caracteres de las cadenas se comparan según sus códigos ASCII. Por ejemplo, la cadena ranger es lexicográficamente más grande que la cadena racecar y la cadena poster es lexicográficamente más grande que la cadena post.

La cadena s=s1s2...s|s| es un palíndromo si coincide con la cadena rev (s) = s|s|s|s|1...s1. En otras palabras, una cadena es un palíndromo si se lee de la misma manera de izquierda a derecha y de derecha a izquierda. Por ejemplo, son cadenas palindrómicas racecar, refer y z.

Entrada

La única línea de entrada contiene una cadena no vacía s que consta solo de letras minúsculas en inglés. Su longitud no supera los 10 caracteres.

Salida

Imprima la subsecuencia palindrómica lexicográficamente más grande de la cadena s.

Ejemplo de Entrada 1

Copy
radar

Ejemplo de Salida 1

Copy
rr

Ejemplo de Entrada 2

Copy
bowwowwow

Ejemplo de Salida 2

Copy
wwwww

Ejemplo de Entrada 3

Copy
codeforces

Ejemplo de Salida 3

Copy
s

Ejemplo de Entrada 4

Copy
mississipp

Ejemplo de Salida 4

Copy
ssss

Explicación

Entre todas las subsecuencias distintas de la cadena radar, las siguientes son palíndromos: a, d, r, aa, rr, ada, rar, rdr, raar y radar. La más grande lexicográficamente de ellos es rr.


Comments

There are no comments at the moment.