完美的代价

问题描述

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

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

　　例如mamad

　　第一次交换 ad: mamda

　　第二次交换 md: madma

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

输入格式

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

　　第二行是一个字符串，长度为N.只包含小写字母

输出格式

　　如果可能，输出最少的交换次数。

　　否则输出Impossible

样例输入

5

mamad

样例输出

3

public static void main(String args[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); String s=sc.next(); char a[]=s.toCharArray(); int b[]=new int[26]; int j; int k=0; char x='0'; for(int i=0;i<n;i++){ j=a[i]-'a'; b[j]++; } for(int i=0;i<26;i++){ if(b[i]%2!=0){ k++; x=(char)(i+'a'); } } if(k>=2){ System.out.println("Impossible"); } else { System.out.println(changes(a,x,n)); } } public static long changes(char s[],char x,int n){ int i,j,k, change=0; for(i=0;i<n/2;i++){ if(s[i]==x){ for(j=i;j<n-i-1;j++) if(s[n-i-1]==s[j]){ break; } change=change+j-i; for(k=j;k>i;k--) s[k]=s[k-1]; s[i]=s[n-i-1]; } else{ for(j=n-i-1;j>=i;j--) if(s[i]==s[j]) break; change=change+n-i-1-j; for(k=j;k<n-i-1;k++) s[k]=s[k+1]; s[n-i-1]=s[i]; } } return change; }