P3808. 字符串拼接

解题思路

核心思路

本题数据量不大，虽然只是要求枚举数量而不是枚举具体的字符串，但仍然可以通过回溯来解决。

注意到在本题中，原输入字符串 s 中的字符顺序并不重要，只有出现次数是关键信息。 所以很容易考虑应该使用哈希表计数器来统计 s 中各个字符出现的次数。即：

与经典全排列问题的区别

特别注意，由于本题存在重复字符，而重复字符可能会导致重复的排列。 因此相比起 经典题型、全排列，本题在问题的定义上更加接近 经典题型、全排列 II。

回溯函数的设计

回溯的重点在于回溯函数的编写。函数传参需要包含三个参数：

• n：目标字符串的长度
• path：当前所选择的路径字符串的情况
• cnt：原字符串 s 中的字符剩余情况

递归终止条件

显然当 len(path) == n 时，我们找到了一个长度为 n 的拼接字符串，更新 ans 并退出递归，即：

横向遍历过程

我们需要考虑 cnt 中的所有 key 以及这些 key 的 value。当：

• value == 0 时，说明 key 这个字符已经在之前被选择完了，无法再选
• path and key == path[-1] 时，说明此时 key 和当前 path 的最后一个字符一致，此时是不能够选择 key 延长在 path 的后面的

对于上述两种情况，都可以直接跳过该 (key, value) 对。

当不满足上述情况时，则可以进行状态更新和回溯，以及回溯结束后的回滚操作。即：

完整的回溯函数

综上，整体的回溯函数为：

这就完成了本题的核心递归函数。

主函数与入口

至于递归入口，则传入 path = "" 即可。 另外题目说明当出现非法输入时需要返回 0，因此还需要判断 s 中的每一个字符是否均为小写字符。 故主函数部分为：

另一种实现方式

当然，本题也可以不借助哈希表，直接使用类似课上讲过的 经典题型、全排列 II 的去重方法，来避免出现重复统计的问题。即：

PS：感兴趣的同学可以思考一下如何使用 dp 完成这个问题。

复杂度分析

• 设原字符总数为 M（题目限定 M ≤ 30），其中不同字符种类数为 k（均为小写字母，故 k ≤ 26），目标串长度为 N（N ≤ 5）。
• 回溯状态树深度为 N；每层横向遍历计数哈希表的全部 k 个键，故分支数上界为 k，状态树节点总数上界为 O(k^N)，每个节点又要花 O(k) 扫描哈希表，总时间上界为 O(k^(N+1))。按 k = 26、N = 5 计也在可接受范围，且「剩余次数为 0」与「和 path 末尾字符相同」两条跳过规则会大幅裁剪实际分支。
• Java 版每层用 new StringBuilder(path).append(k) 复制一份路径，C++ 版的 path + k 同理，单次代价 O(N)，只在渐进上乘一个 N ≤ 5 的小因子。
• 空间复杂度为 O(k + N)：计数哈希表占 O(k)，递归深度为 O(N)。