分数: 400 点
问题陈述
我们有一个字符串 s 由小写英文字母组成。 Snuke可以重复执行以下操作:
- 插入一封信
x到任意位置 s 他选择的,包括开头和结尾 s.
Snuke 的目标是转向 s 变成回文。 确定目标是否可以实现。如果可以实现,找出所需的最少操作数。
注释
A 回文 是一个字符串,向前和向后读取相同。
例如, a, aa, abba 和 abcba 是回文,而 ab, abab 和 abcda 不是。
约束
- 1 \leq |s| \leq 10^5
- s 由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
s
输出
如果目标可以实现,请打印所需的操作数。
如果不是,则打印 -1 。
示例输入 1
xabxa
示例输出 1
2
一种解决方案如下(新插入 x 以粗体显示):
xabxa → xaxbxa → xaxbxax
示例输入 2
ab
示例输出 2
-1
没有操作顺序可以转动 s 变成回文。
示例输入 3
a
示例输出 3
0
s 从一开始就是一个回文。
示例输入 4
oxxx
示例输出 4
3
一种解决方案如下:
oxxx → xoxxx → xxoxxx → xxxxxxx