JUSTAPAL - Just a Palindrome
A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left.
Chiaki has a string $s$ and she can perform the following operation at most once:
- choose two integer $i$ and $j$ ($1 \le i, j \le |s|$).
- swap $s_i$ and $s_j$.
Chiaki would like to know the longest palindromic substring of string after the operation.
There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains a non-empty string $s$ ($1 \le |s| \le 10^6$) consisting of lowercase and uppercase letters.
It is guaranteed that the sum of all $|s|$ does not exceed $10^6$.
For each test case, output an integer denoting the answer.
10 a xxxx ssfs aaabbacaa missimxx ababababgg dfsfsdgdg asdsasdswe chiaki teretwer
1 4 3 8 6 9 6 9 3 6
sparse bit vector for marking visited palindrome centers, 52 linkedlists walk from beginning in outer loop and from end in inner loop, eliminate visited beginnings from list. keep longest candidates in heap, when maximum shorter than longest print answer.
@abhishek_19 operations can be performed at most once. Read the question properly.
@shubham_001 @abhishek_19 Maybe you both mistake substring with subsequence.
@abhishek_19 is quite right I think, in "teretwer" if we swap last t and last r , we have "tererwet" now ans is "tereret" which is of length 7
I think you didn't understand the at most one swap part... You can make a swap or no swaps at all and those are the only options. teretwer you swap the w for the first t.... weretter making a maximum palindrome of six characters -> retter...
"teretwer" answer to this string should be 7 . Answer is 'tereret' this is the longest substring after changes.