给定一个字符串，我们需要找出将其转换为回文串所需的最小交换次数。
Ex-
Given string: ntiin
Palindrome: nitin
Minimum number of swaps: 1
如果无法将其转换为回文，返回-1。
我只能想到一种brute force的方法。我们可以检查第一个和最后一个字符是否相等，如果相等，则检查较小的子字符串，然后对其应用brute force。但这将具有非常高的复杂度，我认为这个问题可以用另一种方式解决。也许可以使用动态规划。如何处理？
首先，您可以检查字符串是否可以转换为回文字符串。
只需使用字母数组（如果所有字母都是拉丁小写字母，则为26个字符），并计算输入字符串中每个字母的数量。
如果字符串长度为偶数，则所有字母计数应为偶数。
如果字符串长度为奇数，则所有字母计数应该全部是偶数，除了一个。
这个第一遍 O(n) 的处理就已经解决了所有 -1 的情况。
如果字符串长度为奇数，请从将具有奇数计数的元素移动到中间开始。
然后，您可以应用以下过程：
使用以下逻辑为长度为 N 的输入字符串 S 建立加权图：
对于索引从 0 到 N/2-1 的每个元素：
- 如果对称元素 S[N-index-1] 相同，则继续
- 如果不同，则在两个字符之间创建边（按字母顺序），或增加现有字符的权重
这个想法是当权重为偶数时，您可以通过一次交换形成两个对。 当权重为奇数时，您不能在一次交换中放置两个对，您的交换需要形成一个循环。
1. For instance "a b a b"
One edge between a,b of weight 2:
a - b (2)
Return 1
2. For instance: "a b c b a c"
a - c (1)
b - a (1)
c - b (1)
See the cycle: a - b, b - c, c - a
After a swap of a,c you get:
a - a (1)
b - c (1)
c - b (1)
Which is after ignoring first one and merge 2 & 3:
c - b (2)
Which is even, you get to the result in one swap
Return 2
3. For instance: "a b c a b c"
a - c (2)
One swap and you are good
在生成图表后，基本上要将每个边的权重/2（整数除法，例如7/3=3）添加到结果中
此外，要查找循环，并将每个循环的长度-1添加到结果中
有相同的问题已经被问过！ https://www.codechef.com/problems/ENCD12
我用这个解决方案AC了 https://www.ideone.com/8wF9DT
//minimum adjacent swaps to make a string to its palindrome
#include<bits/stdc++.h>
using namespace std;
bool check(string s)
{
int n=s.length();
map<char,int> m;
for(auto i:s)
{
m[i]++;
}
int cnt=0;
for(auto i=m.begin();i!=m.end();i++)
{
if(i->second%2)
{
cnt++;
}
}
if(n%2&&cnt==1){return true;}
if(!(n%2)&&cnt==0){return true;}
return false;
}
int main()
{
string a;
while(cin>>a)
{
if(a[0]=='0')
{
break;
}
string s;s=a;
int n=s.length();
//first check if
int cnt=0;
bool ini=false;
if(n%2){ini=true;}
if(check(s))
{
for(int i=0;i<n/2;i++)
{
bool fl=false;
int j=0;
for(j=n-1-i;j>i;j--)
{
if(s[j]==s[i])
{
fl=true;
for(int k=j;k<n-1-i;k++)
{
swap(s[k],s[k+1]);
cnt++;
// cout<<cnt<<endl<<flush;
}
// cout<<" "<<i<<" "<<cnt<<endl<<flush;
break;
}
}
if(!fl&&ini)
{
for(int k=i;k<n/2;k++)
{
swap(s[k],s[k+1]);
cnt++;
}
// cout<<cnt<<" "<<i<<" "<<endl<<flush;
}
}
cout<<cnt<<endl;
}
else{
cout<<"Impossible"<<endl;
}
}
}
希望能帮到你！
我的代码背后的技术是贪心算法 首先检查字符串是否存在回文字符串，如果存在 有两种情况，一种是当字符串长度为奇数时，只有一个字符的计数必须是奇数 而如果是偶数，则没有任何计数应该是奇数 然后从索引0到n/2-1执行以下操作： 固定这个字符并从n-i-1到i+1搜索此字符 如果找到，则将其从该位置（假设为j）交换到其新位置n-i-1 如果字符串长度为奇数，则每次遇到没有其他出现的字符时将其移动到第n/2个位置。
我的解决方案围绕回文属性展开，即第一个元素和最后一个元素应该匹配，如果它们的相邻元素也不匹配，则不是回文。继续比较和交换，直到两个元素到达相同的元素或相邻元素。
以下是Java书写的解决方案:
public static void main(String args[]){
String input = "natinat";
char[] arr = input.toCharArray();
int swap = 0;
int i = 0;
int j = arr.length-1;
char temp;
while(i<j){
if(arr[i] != arr[j]){
if(arr[i+1] == arr[j]){
//swap i and i+1 and increment i, decrement j, swap++
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
i++;j--;
swap++;
} else if(arr[i] == arr[j-1]){
//swap j and j-1 and increment i, decrement j, swap++
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
i++;j--;
swap++;
} else if(arr[i+1] == arr[j-1] && i+1 != j-1){
//swap i and i+1, swap j and j-1 and increment i, decrement j, swap+2
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
i++;j--;
swap = swap+2;
}else{
swap = -1;break;
}
} else{
//increment i, decrement j
i++;j--;
}
}
System.out.println("No Of Swaps: "+swap);
}
我在Java中的解决方案适用于任何类型的字符串，例如二进制字符串、数字等。
public int countSwapInPalindrome(String s){
int length = s.length();
if (length == 0 || length == 1) return -1;
char[] str = s.toCharArray();
int start = 0, end = length - 1;
int count = 0;
while (start < end) {
if (str[start] != str[end]){
boolean isSwapped = false;
for (int i = start + 1; i < end; i++){
if (str[start] == str[i]){
char temp = str[i];
str[i] = str[end];
str[end] = temp;
count++;
isSwapped = true;
break;
}else if (str[end] == str[i]){
char temp = str[i];
str[i] = str[start];
str[start] = temp;
count++;
isSwapped = true;
break;
}
}
if (!isSwapped) return -1;
}
start++;
end--;
}
return (s.equals(String.valueOf(str))) ? -1 : count;
}
希望它有所帮助
string s;
cin>>s;
int n = s.size(),odd=0;
vi cnt(26,0);
unordered_map<int,set<int>>mp;
for(int i=0;i<n;i++){
cnt[s[i]-'a']++;
mp[s[i]-'a'].insert(i);
}
for(int i=0;i<26;i++){
if(cnt[i]&1) odd++;
}
int ans=0;
if((n&1 && odd == 1)|| ((n&1) == 0 && odd == 0)){
int left=0,right=n-1;
while(left < right){
if(s[left] == s[right]){
cnt[left]--;
cnt[right]--;
mp[s[left]-'a'].erase(left);
mp[s[right]-'a'].erase(right);
left++;
right--;
}else{
if(cnt[left]&1 == 0){
ans++;
int index = *mp[s[left]-'a'].rbegin();
mp[s[left]-'a'].erase(index);
mp[s[right]-'a'].erase(right);
mp[s[right]-'a'].insert(index);
swap(s[right],s[index]);
cnt[left]-=2;
}else{
ans++;
int index = *mp[s[right]-'a'].begin();
mp[s[right]-'a'].erase(index);
mp[s[left]-'a'].erase(left);
mp[s[left]-'a'].insert(index);
swap(s[left],s[index]);
cnt[right]-=2;
}
left++;
right--;
}
}
}else{
// cout<<odd<<" ";
cout<<"-1\n";
return;
}
cout<<ans<<"\n";