题目描述

小美定义一个字符串是平衡串，当且仅当该字符串仅包含两种字符，且两种字符出现的次数相等。例如"ababba"是平衡串。 现在小美拿到了一个仅由小写字母组成的字符串，她想知道该字符串有多少子序列是平衡串？ 定义子序列为从左到右取若干个字符（可以不连续）组成的字符串。例如，"aca"是"arcaea"的子序列。

思路:数学

因为是子序列，所以统计出每个字符出现次数，只有26种字符。

考虑当前两种字符 a 和 b 分别出现了 x 次和 y 次 ，v = min(x, y) 这两种字符可以构成 a 和 b 均出现相同次数的子序列有： 长度为 2，4，6，8，... ，2v 的这 v 种子序列 ，两种字符分别出现 1，2，3，4，...，v 次

字符 a 和 b 均出现 t 次，对于字符 a 有 C(x, t) 种选择，字符 b 有 C(y, t) 种选择 字符 c 出现 z 次，z >= v ，故对于字符 c 出现 t 次的子序列也有 C(z, t) 次