问题简述

有一天Jerry给Tom出了一道题来考验他。
Jerry给了Tom一个长度为2*n的只包含小写字母的字符串，让Tom将这个字符串任意挑选字符，将其分成两个等长的字符串a和b(对于一个si不能同时被选到a和b中)，然后a要和reverse(b)相同(a和反转后的b相同)，问这样的方案数有多少？Tom有些为难，所以请你来帮帮他吧。

输入一个正整数n，和一个长度为2*n的字符串。

输出方案数。

示例1
输入：
2
“abba”
输出：
4

解题思路

一、直接桉题目意思翻译
设a[]，b[]，输入的字符为m[]，在m中随机取i个数加入a中(i＜=n)，然后未取出来的数设为n[]，再把a取反，把n的中字符逐一取出进行对比看有没有a取反后的那些字符，有就num++，但是有一种可能如输入字符为aaaa的情况，这时候就只有俩种结果，也就是a，或者aa，即取m[2]m[3]，或者m[3]m[4]是一样的，所以b[]里面要存所有num++的结果，里面的单个元素为如’abbba’形式，然后逐一对比看有没有一样的元素，有num–，继续对比，直至b中元素全不相同

二、按题目中隐含的逻辑编写
其实直接计数m[]中，a~z字符的个数，大于2个的字符都num++，这就是只取一个字符的所有情况，然后看有几种不同的字符，计入i中，再分别考虑取2-i个字符的情况，也就是分别算他们的排列组合，数学问题，一套公式就行了

总结

第二种方式运算起来比第一种会快很多(虽然感觉不出来)/doge

代码展示

package solution106;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {

     public static int[] getCha(int[] arr2,int n){
        int[] arr1 = new int[2*n];
        
        for(int key = 0;key<2*n;key++){
            arr1[key] = key;
        }

        int[] arr3 = new int[n];
        int k = 0;
        boolean flag = false;
        for(int i= 0;i<arr1.length;i++){
            for(int j = 0;j<arr2.length;j++){
                if(arr1[i] == arr2[j]){
                    flag = true;
                    break;
                }
            }
            if(!flag){
                arr3[k] = arr1[i];
                k++;
            }
            flag = false;
        }
        return arr3;
    }

    public static String reverse(String str){
        String new_s1 = "";
        for (int i = str.length() - 1; i >= 0; i--) {
            new_s1 += str.charAt(i);
        }
        return new_s1;
    }

    public static int getSameCount(int a, int b) {
        if(a==1){
            return 1;
        }else{
            if(a > b) {
                return a * getSameCount(a - 1, b);
            }else{
                return a;
            }
        }
    }
	
    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new LinkedList<>();
        boolean[] f = new boolean[n];
        List<Integer> tmp = new ArrayList<>(k);

        dfs(k, 0, n, f, tmp, res);

        return res;
    }
    private static void dfs(int left, int s, int n, boolean[] f, List<Integer> tmp, List<List<Integer>> res) {
        if(0 == left) {
            res.add(tmp);
            return;
        }

        for(int i = s; i < n; i++) {
            if(f[i])
                continue;

            f[i] = true;
            List<Integer> t = new ArrayList<>(tmp);
            t.add(i+1);
            dfs(left-1, i+1, n, f, t, res);

            f[i] = false;
        }
    }
    
    public long solution(int n, String s) {
      
        int count = 0;
        if(s.length() == 2 && s.substring(0,n).equals(s.substring(n,2*n))){
            count = 2;
        }else if(s.substring(0,n).equals(s.substring(n,2*n))){
            count = getSameCount(2*n,n+1)/2;
        }else {
        	List result = combine(2*n,n);

        	char[] array = s.toCharArray();

        	String a = "";
        	String b = "";
            for (int i = 0; i < result.size(); i++) {

                List temp = (List) result.get(i);
                int[] arr2 = new int[n];

                for (int j = 0; j < n; j++) {
                    a = a + array[(int) temp.get(j) - 1];
                    arr2[j] = (int) temp.get(j) - 1;
                }
				
                int[] arr3 = getCha(arr2, n);

                for (int k = 0; k < n; k++) {
                    b = b + array[arr3[k]];
                }
				
                if (a.equals(reverse(b))) {
                    count++;
                }
                a = "";
                b = "";
            }
        }
        return count;
    }
}