阿里云高校学生计划，向全国高校学生免费提供ECS云服务器，完成学生认证即可领取，现在领取还可享受免费续费。还有实践训练营、免费AI资源等你来体验，项目经历、组队参赛、考试认证一网打尽。本网站就使用的是阿里云高校计划免费领取的云服务器搭建的哦。
有一天Jerry给Tom出了一道题来考验他。Jerry给了Tom一个长度为2
*n的只包含小写字母的字符串，让Tom将这个字符串任意挑选字符，将其分成两个等长的字符串a和b(对于一个si不能同时被选到a和b中)，然后a要和reverse(b)相同(a和反转后的b相同)，问这样的方案数有多少？Tom有些为难，所以请你来帮帮他吧。输入一个正整数n，和一个长度为2*n的字符串，输出方案数
输入输出样例如下：
输入：
2
"abba"
输出：
4
题目分析：题目的意思是，有一个长度为2*n的字符串，我们要将其分成两组，每一组放n个字符，至于怎么放是任意的，但是同一个字符不能同时放在两组当中，必须是唯一的。于是就会有很多种放法，如果放在两组中的字符是对称的，比如abbc和cbba，则满足题意，题目求的就是有多少种像这样满足题意的情况。
解题思路：因为字符串中的字符，是等分为两组的，每组可以任意放置字符，因此我们并不需要在意字符串中每个字符的顺序，可以直接统计出这个字符串有多少种字母，每一种字母有多少个，然后进行排列组合就可以了。
因此我们可以选择HashMap或者TreeMap结构来存储每一种字母有多少个，其中key为字符串中出现了的字母，value为该字母对应的出现个数。
综上所述，我选择了HashMap<Character,Integer>来存储字符串中的每一种字母以及其个数。
此时会有两种特殊情况，第一种情况是如果某一种字母的在字符串中为奇数个，则无论如何也不可能放在两组之后，两组的字符串序列是对称的，此时可以直接返回0；第二种情况是，如果字符串中的字符全部为同一个字符，则无论怎么放置，两组字符串序列都是对称的，此时要使用高中的排列组合知识直接计算有多少种情况。
排除以上两种特殊情况后，就剩下一般情况了，需要用到深度优先搜索算法(DFS)来计算有多少种满足题意的情况，由于我个人还没有掌握DFS算法，只知道DFS的大致原理是什么，但是在本题目中以我的能力我讲不清楚此处的DFS算法的原理，还需要继续努力啊。
以上的解题思路，是我在第一期听了学姐和马飞飞大佬讲解后，撰写出来的，没有他们的讲解我可能到现在也毫无头绪，我们要向这些牛人们学习。
package solution106;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Set;
//用于计算组合数的类，来自CSDN
class CombinationNumberCalculation {
public static int[] factor(int n) {
if (n < 0) {
throw new IllegalArgumentException("N must be a non negative integer.");
}
if (n < 4) {
return new int[]{n};
}
int factorNums = (int) (Math.log(Integer.highestOneBit(n)) / Math.log(2));
int[] factors = new int[factorNums];
int factorCount = 0;
for (int i = 2; i <= (int) Math.sqrt(n); i++) {
if (n % i == 0) {
factors[factorCount++] = i;
n /= i;
i = 1;
}
}
factors[factorCount++] = n;
return Arrays.copyOf(factors, factorCount);
}
public static long nchoosek(int n, int k) {
if (n > 70 || (n == 70 && k > 25 && k < 45)) {
throw new IllegalArgumentException("N(" + n + ") and k(" + k + ") don't meet the requirements.");
}
k = k > (n - k) ? n - k : k;
if (k <= 1) { // C(n, 0) = 1, C(n, 1) = n
return k == 0 ? 1 : n;
}
int[] divisors = new int[k]; // n - k + 1 : n
int firstDivisor = n - k + 1;
for (int i = 0; i < k; i++) {
divisors[i] = firstDivisor + i;
}
outer:
for (int dividend = 2; dividend <= k; dividend++) {
for (int i = k - 1; i >= 0; i--) {
int divisor = divisors[i];
if (divisor % dividend == 0) {
divisors[i] = divisor / dividend;
continue outer;
}
}
int[] perms = factor(dividend);
for (int perm : perms) {
for (int j = 0; j < k; j++) {
int divisor = divisors[j];
if (divisor % perm == 0) {
divisors[j] = divisor / perm;
break;
}
}
}
}
long cnk = 1L;
for (int i = 0; i < k; i++) {
cnk *= divisors[i];
}
return cnk;
}
}
public class Solution {
private static StringBuilder groupA = new StringBuilder();//A组
private static StringBuilder groupB = new StringBuilder();//B组
private static long count = 0L;//初始化满足题意的个数
//感谢马飞飞
private static void DFS(StringBuilder builder, int index, HashMap<Character, Integer> map, HashMap<Character, Integer> copiedMap) {
//builder:传入的字符串
//index:角标，用于取出字符
//二叉树：每一个字符是一层
//伪算法如下：
//向字符串a中加入字符
//DFS(left)
//向字符串a中减去字符，向b中加入字符
//DFS(right)
//return
//进一步筛选退出：
//如果a的第一个字符的角标大于n-1，退出
//选定所有字符之后，如果不符合比较的条件，退出
//选完所有字符之后，如果字符串a的大小小于n，退出方法
if (index > builder.length() - 1) {
//来到这一步说明A组字符串第一个角标已经大于n-1
if (groupA.length() < builder.length() / 2) {
return;
}
}
//如果恰好遍历完时有合法序列形成，则不返回，执行下面的代码
if (groupA.length() >= builder.length() / 2) {
//合法序列形成，index以及之后的字符要全部加入到groupB中
int strEnd = groupB.length();
for (int i = index; i < builder.length(); i++) {
char ch = builder.charAt(i);
groupB.append(ch);
}
//此时如果A组和反转后的B组相同，则count加1
if (groupA.toString().equals(groupB.reverse().toString())) {
count++;
}
//将B串反转回来，然后清理B字符串
groupB.reverse();
groupB.delete(strEnd, groupB.length());
return;
}
char ch = builder.charAt(index);//获取当前处理的字符
int countAlphabet = copiedMap.get(ch);
groupA.append(ch);
if (countAlphabet > map.get(ch) / 2) {
//合法字符，向左子树遍历
copiedMap.put(ch, --countAlphabet);//用过之后当前字母对应的value要减去1
DFS(builder, index + 1, map, copiedMap);
} else {
copiedMap.put(ch, --countAlphabet);//用过之后当前字母对应的value要减去1
}
groupA.deleteCharAt(groupA.length() - 1);//删除末尾字符
copiedMap.put(ch, ++countAlphabet);//加回来
//遍历右子树
if (index < builder.length() - 1) {
groupB.append(ch);
DFS(builder, index + 1, map, copiedMap);
groupB.deleteCharAt(groupB.length() - 1);//删除末尾字符
return;
}
//如果指针已经到末尾了，就不需要遍历了，返回
return;
}
public static long solution(int n, String s) {
//创建一个StringBuilder容器
StringBuilder builder = new StringBuilder();
//将传入的字符串s添加到容器中
builder.append(s);
//因为key不能重复，因此用于统计字符串中出现了的字母，value统计这个字母出现的次数
HashMap<Character, Integer> map = new HashMap<>();
//遍历字符串，统计字符串中每一种字母出现的次数
for (int i = 0; i < 2 * n; i++) {
char c = builder.charAt(i);//逐个扫描字符
int countAlphabet = 0;//统计同一个字母出现次数，作为HashMap中key对应的value，初始化为0
//如果map中已经存储了当前扫描到的字母了，就直接把其对应的value赋值给countAlphabet
if (map.containsKey(c)) {
countAlphabet = map.get(c);
}
//将当前正在扫描到的字母添加到map中，由于key不能重复，如果map中已经存在了当前字母，则只增加value
map.put(c, ++countAlphabet);
}
//System.out.println(map);//测试一下统计出来正不正确
//如果出现某个字母只有奇数个，则此题无解，直接返回0
Set<Character> set = map.keySet();//把所有的键放到集合中
for (Character key : set) {
//如果有任何一个键对应的值不是偶数，则肯定无法对称，直接返回0
if (map.get(key) % 2 != 0) {
return 0;
}
}
//如果传入的字符串只有一个字母，则进行排列组合，公式为C(2n,n),上面写好了相关函数
if (1 == map.size()) {
count = CombinationNumberCalculation.nchoosek(2 * n, n);
return count;
}
//拷贝刚刚统计好的集合map到一个新的集合中，用于记录字符的使用情况
HashMap<Character, Integer> copiedMap = new HashMap<>();
copiedMap.putAll(map);//putAll方法将map集合的键值对复制到新的集合
//调用DFS算法
DFS(builder, 0, map, copiedMap);
return count;
}
}
以上代码，自测能过，提交的话超时，哇的一声就哭了！
