问题 K: 子串翻转回文串

问题 K: 子串翻转回文串

时间限制: 2 Sec  内存限制: 128 MB
提交: 872  解决: 162
[状态] [讨论版] [提交] [命题人:]
题目描述
给一个串 s=s1s2⋯sn,你可以选定其一个非空子串,然后将该子串翻转。具体来说,若选定的子串区间为  [l,r]1≤l≤r≤n,则翻转后该串变为 s1s2⋯sl−1srsr−1⋯slsr+1⋯sn
请你回答仅通过一次上述操作后,s 是否能变成回文串。串 s 是回文串,当且仅当它从左至右读出与从右至左读出完全相同,即 s1s2⋯sn=snsn−1⋯s1
输入
注意:本题包含多组测试数据。
第一行包含一个整数 T(1≤T≤5×105),表示数据组数。
接下来的 T 行,每行包含一个仅由英文小写字母组成的字符串 s,含义见题目描述,且串长 ∣s∣ 满足1≤∣s∣≤5×105
保证字符串总长 ∑∣s∣不超过 5×105


输出
对于每组测试数据,输出一行一个字符串,若仅通过一次操作后 s 能变成回文串,则输出 Yes,否则输出 No,大小写不敏感。
样例输入 Copy
4
abba
bacad
abacbaa
aabadcdca
样例输出 Copy
Yes
No
Yes
Yes
提示
第一组数据中,abba 翻转带下划线的子串得到回文串 abba。
第二组数据中,无论如何翻转子串,都不能得到回文串。
第三组数据中, abacbaa翻转带下划线的子串得到回文串 aabcbaa。
第四组数据中, aabadcdca翻转带下划线的子串得到回文串 acdabadca。