解决方案


方法:计数

思路和算法

让我们试着表述一个特殊等价的字符串 ,通过找到函数 使得

通过交换,我们可以排列偶数索引字母和奇数索引字母。这些排列的特征在于字母的数量:所有这样的排列都有相同的数量,不同的数量会产生不同的排列。

因此,函数 (S 中偶数索引字母的数量,其后是 S 中奇数索引字母的数量)成功地刻画了这一等价关系。

然后,我们统计出满足 的数量。

复杂度分析

  • 时间复杂度:

  • 空间复杂度:,其中 A 的长度。