算法思路

本题要求统计给定字符串（长度 ≤ 10）的所有不同排列中，满足“相邻字符不相等”（即好串）的排列个数。由于长度很小，可以直接枚举所有可能的排列，但需注意重复字符会导致重复排列，因此采用回溯法 + 剪枝：

  • 先统计每个字符出现的频率，然后通过深度优先搜索（DFS）构造字符串。
  • 构造过程中，每一步选择剩余数量大于0且与前一个字符不同的字符，将其频率减1后继续递归，直到构成完整字符串（长度等于原串长度），则计数加1。
  • 这种方法天然避免了重复排列（因为按字符种类进行选择，而不是按位置交换），且通过“与前一个字符不同”的剪枝，只生成好串候选。

算法步骤

  1. 输入处理：读入字符串 s，获取其长度 n。
  2. 频率统计：建立一个大小为26的数组 freq，记录每个小写字母出现的次数。
  3. 初始化计数：ans = 0。
  4. 定义递归函数 backtrack(prev, left)：
    • prev 表示已构造部分最后一个字符（初始时使用一个不属于小写字母的特殊值，如 '#'）。
    • left 表示剩余还需放置的字符个数。
    • 基准情形：如果 left == 0，说明已构成一个完整的好串，ans 增加 1，返回。
    • 选择分支：遍历 26 个小写字母 c：
      • 若 freq[c] > 0 且 c != prev：
        • 将 freq[c] 减 1；
        • 递归调用 backtrack(c, left - 1)；
        • 恢复 freq[c]（回溯）。
  5. 启动递归：调用 backtrack('#', n)。
  6. 输出结果：打印 ans。

复杂度分析

  • 时间复杂度：最坏情况下，字符串由完全不同的字符组成（例如 abcdefghij），此时所有排列都是好串，总排列数为 n!。回溯树中叶子节点数为 n!，内部节点总数约为 n! * e，每个节点需要遍历最多 26 个字符（常数），因此时间复杂度为 O(n! * 26) ≈ O(n!)。当 n = 10 时，10! = 3,628,800，计算量在千万级别，可以快速完成。
  • 空间复杂度：递归深度最大为 n，系统栈空间为 O(n)；频率数组占用常数空间 O(26)。总体空间复杂度为 O(n)。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = s.size();

    array<int, 26> freq{};
    for (char c : s) {
        freq[c - 'a']++;
    }

    ll ans = 0LL;

    function<void(char, int)> backtrack = [&](char prev, int left) -> void {
        if (left == 0) {
            ans++;
            return;
        }
        for (int i = 0; i < 26; i++) {
            char c = 'a' + i;
            if (freq[i] > 0 && c != prev) {
                freq[i]--;
                backtrack(c, left - 1);
                freq[i]++;
            }
        }
    };

    backtrack('#', n);
    cout << ans << endl;
}