链接：https://www.dotcpp.com/oj/problem1467.html

题目

回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。

交换的定义是：交换两个相邻的字符

例如mamad

第一次交换 ad : mamda

第二次交换 md : madma

第三次交换 ma : madam (回文！完美！)

输入
第一行是一个整数N，表示接下来的字符串的长度(N < = 8000)

第二行是一个字符串，长度为N.只包含小写字母
输出
如果可能，输出最少的交换次数。

否则输出Impossible
样例输入
5
mamad
样例输出
3

思路讲解

先判断是否可以通过交换形成回文字符串。判断的方式很简单，回文串是对称的，字母两两配对，最后应该没有或只有一个出现次数为奇数的字母。
所以只需要对字符串遍历计数，最后查找出现次数为奇数的字母个数，如果大于或等于2，则无法形成回文串，否则一定可以形成回文串。

然后从外部开始向内，因为内部的改变不影响外部已排好的序列，不会产生重复。

找到中点(l+1)/2 （l为字符串长度，l从1开始）：i<(l+1)/2，i从0开始，这个可以自己试一下

从左边第一个作为定点（不移动位置）开始，查找自右第一个往左找到相同字母，将相同字母移动到回文对应位置，记录交换次数

从左边第二个作为定点开始，查找自右第二个往左找到相同字母，将相同的字母移动到对应的位置，记录交换次数

以此类推。

注意：在这个过程中不改变外部排好的序列，外部已排好的下次查找可直接略过。（见3）

如图：最少交换次数为3

如果存在字母在未排序内找不到相同字母（即单个的奇数字母），或者单个的字母出现在字符串中点左边（在右边时会因为各个字母的交换而最后被换到中点位置去）

//比如h出现3次，则在字符串中最靠左与最靠右（交换次数最少）的h可配成一对回文，剩下一个放中点位置

先不移动，计算该字母到中点所需交换次数，然后将它忽略，继续从它下个字母进行回文排列

注意：

此时对应位置发生改变

//比如一个长度为7的字符串，若左边第一个字母即为单个的奇数字母，那么左边第二个字母对应的回文的位置为右边第一个

当后面字符串形成回文时，再移动该奇数字母至中点位置

//若先移动，则每个字母排序时交换的次数+1

如图：最少交换次数为6

题解

#include<bits/stdc++.h>
using namespace std;
int f(string s) //判断出现次数为奇数的字母个数是否大于2，如果是，则不能构成回文 
{
	int a[26]={0};
	int flag=0;
	for(int i=0;i<s.size();i++){
		a[s[i]-'a']++;
	}
	for(int i=0;i<26;i++){
		if(a[i]%2!=0) flag++;
	}
	if(flag>=2) return 0;
	else return 1;
}
int main()
{
	int n;
	string s;
	cin>>n>>s;
	if(f(s)==0)
	{
		cout<<"Impossible";
		return 0;
	}
	int ans=0;  //记录交换次数 
	int m=0;    //记录奇数字母交换到最中间所需要的次数
	int g=n;    //字符串长度 
	for(int i=0;i<(n+1)/2;i++)
	{
		g--;
		int j;
		for(j=g;j>i;j--)
		{
			if(s[j]==s[i])
			{   //如果找到 
				for(int k=j;k<g;k++)
				{   //一直向右移动到对称的位置 
					char t=s[k];
					s[k]=s[k+1];
					s[k+1]=t;
					ans++;	
				}
				break;
			}
		}
		//如果没找到，则当前字母是唯一的奇数字母
		if(j==i)   //判断条件，当没有找到时，循环已经向左判断直到i和j重合 
		{
			m=(n+1)/2-i-1;		//记下移动到最中间所需的次数
			g++;				//找到奇数字母之后，对称序列发生变化 
		}
	}
	ans+=m;
	cout<<ans; 
	return 0;
}

参考博文链接：https://blog.csdn.net/qq_40605470/article/details/79268979