#P1854. Evil Straw Warts Live
Evil Straw Warts Live
本题没有可用的提交语言。
题目描述
回文串是指正读反读都相同的字符串。给定一个任意字符串(不一定是回文),计算通过相邻字符交换将其转换为回文串所需的最少交换次数。每次交换定义为反转两个相邻字符的顺序。
例如,字符串 "mamad"
可以通过以下次交换变为回文串 "madam"
:
. 交换 "ad"
→ "mamda"
. 交换 "md"
→ "madma"
. 交换 "ma"
→ "madam"
输入格式
第一行:测试用例数量。
接下来行:每行一个长度不超过的小写字母字符串。
输出格式
对于每个测试用例,输出最少交换次数;若无法转换为回文串,输出 "Impossible"
。
样例输入 1
3
mamad
asflkj
aabb
样例输出 1
3
Impossible
2
来源
Waterloo local 2004.09.19
关键思路
. 回文可行性检查:统计字符频率,若超过一个字符出现奇数次,则无法构成回文。
. 贪心交换策略:
从字符串两端向中间遍历,若两端字符不同,则在内侧找到匹配字符并通过相邻交换移至对应位置。
每次交换的步数计入总次数。
. 奇数长度处理:若字符串长度为奇数,允许中心字符不匹配,但需确保其余字符成对出现。
示例解析
"mamad"
:
步骤1:左'm'
=右'd'
→ 交换'a'
和'd'
("mamda"
,次)。
步骤2:左'a'
≠右'a'
→ 交换'm'
和'd'
("madma"
,次)。
步骤3:左'm'
≠右'm'
→ 交换'a'
和'm'
("madam"
,次)。
"asflkj"
:字符频率不满足回文条件,直接输出 "Impossible"
。
"aabb"
:通过交换'b'
和相邻字符(次)得到 "abba"
。