LCC '21 Contest 1 S2 - Tracy's Palindromes

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Tracy has a string of N lowercase alphabetical characters. She would like to choose a point on her string between two characters to be the center of a special palindrome. She can remove characters from the beginning or end of the string to make her special palindrome.

A palindrome is defined as special if it has 2 of the same letter in the center, and each letter from the center is repeated i + 2 times, where i is the distance from the center. That is, the center of the palindrome should have 2 of the same letter, then 3, then 4, and so on. In addition, each repeated section of the same letter should be of a different letter than those adjacent to it.

Can you output the length of the longest special palindrome Tracy can make?

Input Specification

The first line will contain one integer N (1 \leq N \leq 6 \times 10^3), the length of Tracy's string.

The next line will contain N lowercase alphabetical characters, Tracy's string.

Output Specification

Output a single integer, the length of the longest special palindrome Tracy can make. If Tracy cannot make a special palindrome, output -1.

Sample Input 1


Sample Output 1


Explanation for Sample 1

The longest special palindrome Tracy can make is ddddbbbzzbbbdddd.

Sample Input 2


Sample Output 2



There are no comments at the moment.