蓝桥杯VIP 完美的代价 递归简洁明了

package practise;

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.Stack;


public class Main {
	static int N;
	static char[] ch;
	static int count = 0;
	static Scanner sc = new Scanner(new InputStreamReader(System.in));
    static OutputStreamWriter out = new OutputStreamWriter(System.out);
	public static void main(String[] args) throws Exception  {
		N = sc.nextInt();
		ch = sc.next().toCharArray();
		int[] helpNum = new int[26];//辅助数组判断几个字符是奇数
		for (char c : ch) {
			helpNum[c-'a']++;
		}
		for (int i = 0,t = 0; i < helpNum.length; i++) {
			if((helpNum[i]&1)==1){
				if(++t>1){
					out.write("Impossible"); 
					out.flush();
					return;
				}
				
			}
		}
		for (int i = 0; i < N/2; i++) {
			change(lastIndex(i),N-1-i);
		}
		System.out.println(count);
        
    }
	
	
	//查找最后一个字符的下标位置
	public static int lastIndex(int cur){
		for (int i = N-1-cur; i > cur; i--) {
			if(ch[i]==ch[cur]){
				return i;
			}
		}
		//如果奇数字符在第一个位置，则将其与第二个位置交换再查找。
		change(cur,cur+1);
		return lastIndex(cur);
		
	}
	//查找到之后交换
	public static void change(int start,int end){
		if(ch[start]==ch[end])
			return;
		ch[start] = (char) (ch[start]^ch[start+1]);
		ch[start+1] = (char) (ch[start]^ch[start+1]);
		ch[start] = (char) (ch[start]^ch[start+1]);
		count++;
		change(start+1,end);
	}
	
}