高校计划简介
为响应“新基建，新人才”号召，阿里云推出高校计划，向全国高校学生、教师免费提供 2.68 亿小时云服务器 ECS 算力，及“学练赛考”技术成长赋能体系。陪伴两千多所高校的在校生云上实践、云上成长。点击高校计划立即申请。

我在阿里云高校计划参加了 ECS 训练营进阶班，赠送了价值 600 元的阿里云大数据助理工程师认证（ACA），希望大家感兴趣的话也来报名训练营，让我们一起当校友吧。

106.Jerry 的考验

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

输入：一个正整数 n，一个长度为 2 * n 的字符串。
输出：方案数。

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

解题思路描述

点击查看：笔试算法模拟题精解之“Jerry 的考验”。
本题的关键在于理解题意：所谓挑选 n 个字符变成 a 和 b 两个字符串，是指 在原字符串中抽出 n 个字符，这些字符的的顺序保持不变，剩下字符的顺序也保持不变，由此组成 a 和 b 两个字符串。

例如 “abcdef”，挑选第 2、3、5 个字符，则分成 “bce” 和 “adf” 两个串。

接下来是整理的思路解析：整体框架是 dfs，枚举每个字符属于 a 还是属于 b，搜索过程中需要利用 a 和 b 的对称性做加速处理，否则会超时。

比方说：
xcccddcccxdd

从左往右枚举 a 字符串的构成，如果令第一个 x 属于 a，根据对称性，倒数第三个字符 x 一定是属于 b；如此推导出末尾的 dd 一定属于 a，中间位置的 dd 一定属于 b，而且是 b 的头两个字符；然后左边 ccc 一定 a，右边 ccc 一定是 b，由此得出 1 种方案。令第一个 x 属于 b 也可以用同样的方式得到 1 种方案。

用这个思路直接写代码不太好写，可以通过枚举二进制，固定左半边的选择情况，然后对于每一个 case，通过 dfs 搜索右半边有多少种合法组合，搜索过程中利用对称性进行剪枝。

对于字符全部相同 case 如 ”aaaaaaaa”，因为过程中无法剪枝，会退化成 2^(2*n)。对于这种 case，答案就是 C(2n,n)，预判一下直接返回即可。

分析

可以看出，对于字符串 abba， 分成两个等长的字符串 a 和 b，并且 a 和反转后的 b 相同，一共有四种方案。

源码：
功能实现但是超时，不献丑了，我是 five。