Problem K
Swap for Palindrome
Eric is a cool kid who just learned that a palindrome is a string that reads the same forward and backward. Recently, he found a string consisting of $n$ lowercase English letters. He immediately started looking for palindromic substrings in it (a substring is a contiguous sequence of characters within a string). He soon realized that the string did not contain very long palindromic substrings.
Eric wants to improve the situation by performing exactly one swap of two letters in the string (the letters must be at different positions). What is the length of the longest palindromic substring that can be obtained after Eric performs exactly one swap?
Input
The input consists of a single string containing at least $2$ and at most $5\, 000$ lowercase English letters (a-z).
Output
Output a single integer, the length of the longest palindromic substring that Eric can obtain after exactly one swap.
Explanation of Sample Case 1
Eric can swap the first c with the first a, i.e., ccbaada. The resulting string is acbcada, which has a palindromic substring of length $5$: acbca.
| Sample Input 1 | Sample Output 1 |
|---|---|
ccbaada |
5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
ab |
1 |
