字符串排列计数优化：如何突破O(N*N!)复杂度限制

步骤1：前置合法性判断 #

先统计输入字符串中元音（aeiou）的数量v、辅音的数量c：

• 若c != v且c != v + 1，直接返回0。因为辅音开头的交替排列，要么辅音比元音多1个（对应奇数长度的C-V-C...-C结构），要么两者数量相等（对应偶数长度的C-V-C...-V结构），其他情况必然出现连续的元音或辅音。
• 例：输入AAB时，v=2、c=1，c < v，直接返回0，符合示例结果。

步骤2：计算带重复元素的排列数 #

对于存在重复元素的字符组，不同排列数的计算公式为：

总排列数 = 组内元素总数的阶乘 ÷（组内每个元素重复次数的阶乘之积）

具体实现：

• 用哈希表或数组统计元音组中每个字符的出现次数，辅音组同理。
• 计算元音排列数：先求v!，再除以每个元音重复次数的阶乘。
• 计算辅音排列数：先求c!，再除以每个辅音重复次数的阶乘。

示例：

• 元音组为AAE时，总排列数 = 3! / (2! * 1!) = 3
• 辅音组为BBC时，总排列数 = 3! / (2! * 1!) = 3

步骤3：计算合法排列总数 #

根据c和v的数量关系得出结果：

• 若c == v + 1：合法结构为C-V-C-V-...-C，总排列数 = 辅音排列数 × 元音排列数
• 若c == v：合法结构为C-V-C-V-...-V，总排列数 = 辅音排列数 × 元音排列数

示例验证 #

• 输入BAR：元音A（v=1，无重复），辅音B、R（c=2，无重复）。c = v + 1，辅音排列数2! = 2，元音排列数1! = 1，总结果2×1=2，符合示例。
• 输入BAB：元音A（v=1），辅音B、B（c=2）。辅音排列数2!/(2!)=1，元音排列数1，总结果1×1=1，合法排列仅BAB，正确。
• 输入BBAA：元音AA（v=2），辅音BB（c=2）。c = v，元音排列数2!/(2!)=1，辅音排列数2!/(2!)=1，总结果1×1=1，合法排列为BABA，正确。

复杂度分析 #

整体时间复杂度为O(N)（N为输入字符串长度）：

• 统计字符类型及重复次数：O(N)
• 阶乘计算的时间复杂度为O(max(v,c))，而max(v,c) ≤ N，因此整体仍为线性复杂度。

完全规避了全排列解法的O(N*N!)高复杂度，可高效处理较长字符串。

内容的提问来源于stack exchange，提问作者Zi Ming