LeetCode 3518 最小回文排列 II - Solution

1. 题目数据

题目类型：传统题
题目链接：LeetCode 3518. 最小回文排列 II

2. 题意简述

已知长度为 $n$（$1 \le n \le 10^4$）的回文字符串 $s$（由小写英文字母组成）和整数 $k$（$1 \le k \le 10^6$），求 $s$ 的所有不同回文排列按字典序排序后的第 $k$ 个排列；若排列总数不足 $k$，返回空字符串。

3. 朴素解法

直接生成所有回文排列、去重、排序，取第 $k$ 个。排列数最坏情况为 $\frac{(n/2)!}{\prod cnt[i]!}$，$n=10^4$ 时完全不可行。

4. 核心解法

关键观察：回文串的左半边决定整体

对于任意回文串，右半边完全由左半边镜像得到，中间字符（若存在）固定不变。因此，构造回文排列等价于构造左半边的字符排列。问题就此降维：求可重集合的第 $k$ 小排列。

本题是 LeetCode 3517. 最小回文排列 I 的升级版。I 版只要求字典序最小的回文排列，没有 $k$ 参数：既然左半边决定整体，只需把左半边字符按字典序从小到大排即可。II 版升级为求第 $k$ 小排列，正是本章后续要讨论的可重集合逆康托展开问题。

阶段一：与标准逆康托展开对比，建立算法大框架

在继续之前，有必要明确本题与标准逆康托展开（见【组合数学】康托展开学习笔记）的关键差异。

标准逆康托展开（元素互异）的逐位决策流程是：

维护一个有序的剩余数字集合 $S$（初始为 $1,2,\dots,n$）；
计算权重 $t = \left\lfloor \dfrac{k}{(n-i)!} \right\rfloor$；
用数据结构（线段树 / 树状数组 / 平衡树）在 $S$ 中查第 $t+1$ 小的元素作为当前位；
更新 $k \gets k \bmod (n-i)!$，从 $S$ 中移除已选元素。

核心开销在于维护动态有序集合并支持"第 $K$ 小"查询，因此需要 $O(\log n)$ 的数据结构。

而本题的可重集合逆康托展开，利用了两个关键性质，将流程大幅简化：

维度	标准逆康托（元素互异）	可重集逆康托（本题）
剩余元素的组织方式	有序集合 $S$，需动态维护	频次数组 $cnt[0…25]$，固定大小
"第 $K$ 小"的获取方式	计算权重 $t$，用数据结构查第 $t+1$ 小	直接枚举 $c \in [\texttt{‘a’},\texttt{‘z’}]$，跳过 $cnt[c]=0$ 的字符
当前分支的排列增加量	$(n-i)!$（全排列）	$\displaystyle \binom{rest}{cnt_0}\binom{rest-cnt_0}{cnt_1}\cdots$（多重集排列）

简言之，因为本题的"值域"只有 $26$ 个字母，枚举代替了查第 $K$ 小，不再需要线段树或树状数组；因为元素可重，组合数连乘代替了阶乘，作为每个分支的排列增加量。整个算法变成纯粹的"枚举 + 组合计数 + 试填决策"。

阶段二：分析两种 adds 的计算方法

有了上述框架，我们就可以把标准逆康托的"计算权重 $t$“替换为本题的"逐字母枚举 + 组合计数”。具体来说，对每一位：

维护当前各字符的剩余频次 $cnt[0…25]$。
对每一位，从小到大枚举可选的字母 $c$。
计算"若该位填 $c$，剩余 $rest$ 个位置能产生多少种合法排列"，记为 $adds$。
若当前偏移量 $prk + adds \ge k$，说明第 $k$ 小排列在此分支内，选定 $c$。
否则，说明第 $k$ 小排列排在当前分支之后，执行 $prk \gets prk + adds$（跳过该分支），继续枚举下一个字母。

这里 $adds$ 的含义与标准逆康托中的 $(n-i)!$ 完全相同——都是"当前分支有多少种排列"——但计算方法因可重集合而不同。

标准逆康托（元素互异）：剩余 $rest$ 个互异元素的全排列数为 $rest!$。

本题（可重集合）：给定剩余频次 $cnt[i]$ 和剩余位置 $rest = \sum cnt[i]$，多重集排列数为：

$$ adds = \frac{rest!}{\prod_{i=0}^{25} cnt[i]!} $$

直接计算阶乘不现实（$rest \le 5000$），我们将其转化为组合数连乘：

$$ adds = \binom{rest}{cnt_0} \times \binom{rest - cnt_0}{cnt_1} \times \cdots $$

每次调用时，若中间结果超过 $k$，立即返回 $k+1$（因为我们已经知道该分支的排列数足够大，不需要精确值）。

阶段三：确定组合数细节

现在问题归结为高效计算 $C(n, m)$，且只需判断是否超过 $k$（$k \le 10^6$）。我们使用递推公式：

$$ C(n, m) = C(n, m-1) \times \frac{n - m + 1}{m} $$

这个公式的组合意义是"先乘后除"：先从 $n-m+1$ 个"局外人"中选一个加入现有 $m-1$ 人队伍，再除以 $m$ 消除因添加顺序造成的重复计数。每一步的中间结果都是整数。

在 comb 函数的实现中，我们利用对称性 $m = \min(m, n-m)$ 减少循环次数，并在中间结果超过 $k$ 时立即返回 $k+1$。这既防止了 long long 溢出，又将常数压到最小（因为 $k \le 10^6$，循环最多 20 余次）。

ll comb(ll n, ll m, int k)
{
    m = min(m, n - m);
    ll res = 1;
    for (int i = 1; i <= m; i++)
    {
        res = res * (n - i + 1) / i;
        if (res > k) return k + 1;
    }
    return res;
}

5. 正确性证明

需证三点：试填法的贪心决策正确、$adds$ 计算正确、截断不影响最终结果。

1. 试填法的贪心决策正确。 在每一步，我们将所有字典序比当前选择小的排列按首字符分块，$adds$ 恰好是当前字符对应的块大小。若 $k$ 落在块内（即 $prk + adds \ge k$），则锁定该字符；否则跳过整个块（累加 $prk$）。由于排列按字典序连续分布，此过程最终精确锁定第 $k$ 小排列。

2. $adds$ 计算正确。 给定剩余频次 $cnt[i]$ 和剩余位置 $rest$，排列总数为多重集排列公式 $adds = \dfrac{rest!}{\prod cnt[i]!}$。将其转化为组合数连乘 $adds = \binom{rest}{cnt_0} \binom{rest-cnt_0}{cnt_1} \cdots$，数学上等价，且避免了直接计算阶乘。

3. 截断不影响最终结果。 我们只关心 $adds$ 是否 $\ge k$。m = min(m, n - m) 将 $m$ 映射到 $[0, n/2]$，由杨辉三角的对称性与单调性，$C(n, m)$ 在此区间单调递增，因此中间结果只增不减。一旦超过 $k$，后续步骤不可能回落到 $k$ 以下，截断返回 $k+1$ 不影响 $prk + adds \ge k$ 的判断。calc_adds 的逐项连乘截断同理。

综上所述，算法正确。

6. 复杂度分析

时间复杂度：$O(n \cdot |\Sigma|^2 \cdot \log k)$，其中 $|\Sigma| = 26$ 为字母表大小，$\log k \le 20$ 为 comb 因提前截断的实际迭代次数。由于 $|\Sigma|$ 与 $\log k$ 均为常数，可简化为 $O(n)$。左半长 $L = \lfloor n/2 \rfloor \le 5000$，每层枚举 26 个字母，每次 calc_adds 遍历 26 个字母并调用 comb（最多约 20 次）。总操作量约 $26 \times L \times 26 \times 20 \approx 2.7 \times 10^7$，在时限内。
空间复杂度：$O(26)$ 存储频次，$O(1)$ 额外空间。

7. 实现细节与避坑指南

组合数提前截断：comb(n, m, k) 在中间结果超过 $k$ 时立即返回 $k+1$。这既防止了 long long 溢出，又将常数压到最小（因为 $k \le 10^6$，循环最多 20 余次）。
先乘后除：C(n,m) 的递推实现中，res = res * (n-i+1) / i 保证每一步都是整数，避免浮点误差。
0-index 与 1-index：字符串预处理时加前导空格转为 1-indexed，简化中间字符的下标计算 (n+1)/2。
无解判断：若左半边未填满（res.length() < n/2），说明排列总数不足 $k$，直接返回空串。
中间字符固定：回文排列的中间字符（若存在，即原字符串长度是奇数）必须与原字符串一致，代码中直接取 s[(n+1)/2]。

8. 参考代码

我提交时使用的版本，采用「试填法 + 组合数截断」的思路，在 LeetCode 上已通过。

class Solution {
    using ll = long long;

    // 计算 C(n, m)，若结果 > k 则提前返回 k + 1
    ll comb(ll n, ll m, int k)
    {
        m = min(m, n - m);
        ll res = 1;
        for (int i = 1; i <= m; i++)
        {
            res = res * (n - i + 1) / i;
            if (res > k) return k + 1;
        }
        return res;
    }

public:
    string smallestPalindrome(string s, int k)
    {
        int n = s.length();
        vector<int> cnt(26, 0);
        s = " " + s; // 转为 1-indexed，方便取中间字符

        // 仅统计左半边的字符频次（回文串右半边由左半边镜像决定）
        for (int i = 1; i <= n / 2; i++)
            cnt[s[i] - 'a']++;

        string res = "";

        // 计算在当前频次下，剩余 rest 个位置能产生的排列数
        auto calc_adds = [&](int rest) -> ll
        {
            ll adds = 1;
            for (int i = 0; i < 26; i++)
            {
                adds *= comb(rest, cnt[i], k);
                if (adds > k) return k + 1LL;
                rest -= cnt[i];
            }
            return adds;
        };

        ll prk = 0; // 偏移量：前面已经跳过的排列总数

        // 逐位试填左半边
        for (int i = 1; i <= n / 2; i++)
        {
            for (int j = 0; j < 26; j++)
            {
                if (!cnt[j]) continue;

                cnt[j]--;
                ll adds = calc_adds(n / 2 - i);

                // 若当前偏移 + 该分支的排列数 >= k，说明第 k 小排列在此分支内
                if (prk + adds >= k)
                {
                    res += char('a' + j);
                    break;
                }

                cnt[j]++;
                prk += adds; // 跳过当前分支，累加偏移量
            }
        }

        // 左半边未填满，说明排列总数不足 k
        if (res.length() < n / 2) return "";

        // 奇数长度需补中间字符，再镜像右半边
        if (n & 1)
            return res + s[(n + 1) / 2] + string(res.rbegin(), res.rend());
        return res + string(res.rbegin(), res.rend());
    }
};

9. 补充说明

本题是可重集合逆康托展开的经典应用。更一般地，若题目要求"求第 $k$ 小排列"且元素可重，均可用此框架：逐位枚举、组合计数、试填决策。方法经典，具有学习的价值。

我在写这篇题解时，正是先把可重集合的排列公式 $\frac{rest!}{\prod cnt[i]!}$ 拆成组合数连乘，才真正理解了为什么官方题解用 comb 来计算 $adds$——这个转化是整个算法复杂度正确的基础。

本题是 LeetCode 每日一题，思路清晰且实现友好。试填法的框架一旦建立，代码量很小，主要工作量在组合数的截断优化上。