第 K 小的最小回文排列（进阶版）

题目描述

这是上一篇《最小回文排列 I》的进阶版。上一篇只要最小的那个回文排列，这一篇要第 k 小的那个。

给你一个回文字符串 s 和一个整数 k，返回 s 的所有回文排列中按字典序第 k 小的那个；如果不存在第 k 个，返回空字符串 ""。

  • 回文、排列、字典序这些概念上一篇讲过，不懂先去看上一篇，这里不重复了。（力扣 3518）

解决方法

1. 还是老套路：只看一半

上一篇说过，回文左右两半一样，所以问题就变成了——求半边串的第 k 个排列。这一步完全一样，不重复讲了。

但是！！上一篇只取最小那个，直接从小到大拼 half 就行。这一篇要第 k 个，那排序不能偷懒了，得自己动手算排列数。

所以核心难点就一个：怎么在不去重、不暴力全排列的情况下，算出"以某个字符开头一共有多少种排列"。 下面重点讲这个。

2. 统计频次 + 检查可行性（跟上一篇一样）

老规矩，先数每个字母出现几次，检查能不能构成回文（奇数次字符最多一个）。

vector<int> cnt(26, 0);
for (char c : s) cnt[c - 'a']++;   // 统计每个字符出现的次数

// 检查可行性：最多只能有一个字符出现奇数次
int oddCount = 0;
char midChar = 0;
for (int i = 0; i < 26; i++) {
    if (cnt[i] % 2 == 1) {
        oddCount++;
        midChar = 'a' + i;   // 记录中间字符
    }
}
if (oddCount > 1) return "";   // 超过一个奇数次，无法构成回文

3. 构建半边串的频次（跟上一篇一样）

回文 = 左半边 + （中间字符） + 左半边反转，所以只需要排列左半边。

vector<int> halfCnt(26, 0);   // 半边串里每个字符出现的次数
int total = 0;
for (int i = 0; i < 26; i++) {
    halfCnt[i] = cnt[i] / 2;  // 每个字符取一半
    total += halfCnt[i];      // 半边串的总长度
}

4. 排列数怎么算？（新知识，重点！）

现在要算：用这些字母（可能有重复）能排成多少种不同的串？

这是个经典公式。假设半边串总长度是 total，字符 a 有 f0 个、b 有 f1 个……那么不重复排列数就是：

$$\frac{total!}{f_0! \times f_1! \times f_2! \times \cdots}$$

但直接算阶乘会溢出（数字大得离谱）。更稳的写法是用组合数连乘：

$$C(total, f_0) \times C(total - f_0, f_1) \times C(total - f_0 - f_1, f_2) \times \cdots$$

意思就是：先给 a 挑位置，再给 b 挑位置……每次挑完位置就减少可选位，最后乘起来就是总排列数。

而且这里有个关键技巧：我们只关心它跟 k 比谁大，所以每乘一步就检查一次，一旦超过 k 就立刻返回 k+1（表示"绝对够多了"），这样数字根本不会溢出。

// 计算含重复字符的排列数，超过 k 直接返回 k+1，防溢出
auto countPerms = [&](const vector<int>& freq, int rem) -> long long {
    long long res = 1;
    int remaining = rem;
    for (int i = 0; i < 26 && remaining > 0; i++) {
        if (freq[i] == 0) continue;
        // 用组合数 C(remaining, freq[i]) 连乘
        // 取较小的一方，保证中间值单调递增，截断才安全
        int m = min(freq[i], remaining - freq[i]);
        for (int j = 1; j <= m; j++) {
            res = res * (remaining - j + 1) / j;
            if (res > k) return (long long)k + 1;   // 超过 k 直接返回
        }
        remaining -= freq[i];
    }
    return res;
};

💡 为什么 取 min 更安全？因为 C(n,m) = C(n,n-m)，取较小的一方能让中间计算值尽量小，边乘边除也不容易炸。

5. 逐位构造：从高位开始试探（新知识，重点！）

有了排列数，就能一位一位地"数"出第 k 个了。思路很像"查字典翻页"：

先看 k 有没有超范围，如果 k 大于总排列数，那根本不存在第 k 个，直接返回空。

然后从第 0 位开始，从小到大试每个字母：

  • 假设这一位放 a，用剩下的字母算一算，能排出 perms 种。
  • 如果 k <= perms，说明第 k 个就在 a 开头的这组里，这一位就是 a，锁定它，继续下一位。
  • 如果 k > perms，说明第 k 个不在 a 开头里，跳过整组（k -= perms），试下一个字母。

就这样一位位试探下去，直到拼完整个半边。

// 先判断 k 是否超出总排列数，超出则无解
if (k > countPerms(halfCnt, total)) return "";

string halfStr;
halfStr.reserve(total);

for (int pos = 0; pos < total; pos++) {
    for (int c = 0; c < 26; c++) {
        if (halfCnt[c] == 0) continue;

        halfCnt[c]--;                                    // 暂扣：假设这一位放 'a'+c
        long long perms = countPerms(halfCnt, total - pos - 1);

        if (k <= perms) {
            halfStr.push_back('a' + c);                  // 答案在这一组里，锁定
            break;
        } else {
            k -= perms;                                  // 跳过整组，继续试下一个
            halfCnt[c]++;                                // 恢复：这一位不放它了
        }
    }
}

6. 组装回文（跟上一篇一样）

把 halfStr 反转得到右半部分，中间如果有奇数字符就插进去，拼起来就是答案。

string rev = halfStr;
reverse(rev.begin(), rev.end());

if (oddCount == 1)
    return halfStr + midChar + rev;
else
    return halfStr + rev;

完整代码

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    string smallestPalindrome(string s, int k) {
        // 暴力枚举所有回文排列再排序，思路简单但必超时，不推荐
        // 核心：问题转化为求半边串的第 k 个排列

        // ========== 第一步：统计字符频次 ==========
        vector<int> cnt(26, 0);
        for (char c : s) cnt[c - 'a']++;

        // ========== 第二步：检查可行性 ==========
        // 最多只能有一个字符出现奇数次（放回文正中间）
        int oddCount = 0;
        char midChar = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] % 2 == 1) {
                oddCount++;
                midChar = 'a' + i;
            }
        }
        if (oddCount > 1) return "";   // 不能构成回文

        // ========== 第三步：构建半边串频次 ==========
        vector<int> halfCnt(26, 0);
        int total = 0;
        for (int i = 0; i < 26; i++) {
            halfCnt[i] = cnt[i] / 2;
            total += halfCnt[i];
        }

        // ========== 第四步：排列数计算 ==========
        // 含重复字符排列数 = total! / (f0! * f1! * ...)
        // 用组合数连乘，每步检查是否超过 k，防溢出
        auto countPerms = [&](const vector<int>& freq, int rem) -> long long {
            long long res = 1;
            int remaining = rem;
            for (int i = 0; i < 26 && remaining > 0; i++) {
                if (freq[i] == 0) continue;
                int m = min(freq[i], remaining - freq[i]);
                for (int j = 1; j <= m; j++) {
                    res = res * (remaining - j + 1) / j;
                    if (res > k) return (long long)k + 1;   // 防溢出
                }
                remaining -= freq[i];
            }
            return res;
        };

        // ========== 第五步：逐位构造半边串 ==========
        if (k > countPerms(halfCnt, total)) return "";   // 超出总排列数，无解

        string halfStr;
        halfStr.reserve(total);

        for (int pos = 0; pos < total; pos++) {
            for (int c = 0; c < 26; c++) {
                if (halfCnt[c] == 0) continue;

                halfCnt[c]--;                             // 暂扣
                long long perms = countPerms(halfCnt, total - pos - 1);

                if (k <= perms) {
                    halfStr.push_back('a' + c);           // 答案在这组里
                    break;
                } else {
                    k -= perms;                           // 跳过整组
                    halfCnt[c]++;                         // 恢复
                }
            }
        }

        // ========== 第六步：组装回文 ==========
        string rev = halfStr;
        reverse(rev.begin(), rev.end());

        if (oddCount == 1)
            return halfStr + midChar + rev;
        else
            return halfStr + rev;
    }
};