蓝桥杯训练—完美的代价

---

一、题目

回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换ad：mamda
第二次交换md：madma
第三次交换ma：madam
输入格式：
输入一行，是一个字符串，长度为n，只包括小写字母
输出格式：
如果可能，输出最少的交换次数
否则输出impossible

二、示例

输入：

mamad

输出：

3

三、解析

无需考虑字符串的长度，当每个字母的出现次数都为偶数时，该字符串必定能构成回文串；当字符串中出现奇数个出现次数为奇数的字母时，也能构成回文串；但是当出现偶数个出现次数为奇数的字母时则不能构成回文串。
基于此，可以统计字母出现的次数，以及出现次数为奇数的字母的个数。

四、代码

python代码：

pal = list(input())
n = len(pal)
count = flag = 0
m = n - 1
for i in range(m):for k in range(m, i - 1, -1):if k == i:if n % 2 == 0 or flag == 1:print("impossible")exit()flag = 1count += int(n / 2) - ielif pal[k] == pal[i]:for j in range(k, m):pal[j], pal[j + 1] = pal[j + 1], pal[j]count += 1m -= 1break
print(count)

运行结果：