Score : 400 points
We have a string s consisting of lowercase English letters. Snuke can perform the following operation repeatedly:
x
to any position in s of his choice, including the beginning and end of s.Snuke's objective is to turn s into a palindrome. Determine whether the objective is achievable. If it is achievable, find the minimum number of operations required.
A palindrome is a string that reads the same forward and backward.
For example, a
, aa
, abba
and abcba
are palindromes, while ab
, abab
and abcda
are not.
Input is given from Standard Input in the following format:
s
If the objective is achievable, print the number of operations required.
If it is not, print -1
instead.
xabxa
2
One solution is as follows (newly inserted x
are shown in bold):
xabxa → xaxbxa → xaxbxax
ab
-1
No sequence of operations can turn s into a palindrome.
a
0
s is a palindrome already at the beginning.
oxxx
3
One solution is as follows:
oxxx → xoxxx → xxoxxx → xxxoxxx