Hard
题目描述
给你一个回文字符串 s 和一个整数 k。
返回 s 的第 k 小字典序回文排列。如果不同的回文排列少于 k 个，返回空字符串。
注意：产生相同回文字符串的不同重排被视为相同，只计算一次。
示例 1：
输入：s = "abba", k = 2
输出："baab"
解释：
"abba" 的两个不同回文重排是 "abba" 和 "baab"。
按字典序，"abba" 在 "baab" 之前。由于 k = 2，输出是 "baab"。
示例 2：
输入：s = "aa", k = 2
输出：""
解释：
只有一个回文重排："aa"。
由于 k = 2 超过了可能重排的数量，输出空字符串。
示例 3：
输入：s = "bacab", k = 1
输出："abcba"
解释：
"bacab" 的两个不同回文重排是 "abcba" 和 "bacab"。
按字典序，"abcba" 在 "bacab" 之前。由于 k = 1，输出是 "abcba"。
约束条件：
1 <= s.length <= 10^4s由小写英文字母组成s保证是回文的1 <= k <= 10^6
解题思路
这道题需要找到回文字符串的第 k 小字典序排列。关键思路如下：
核心观察：
- 对于回文字符串，只需要确定前一半字符，后一半由对称性决定
- 统计每个字符的频率，用频率的一半来构造前半部分
- 使用组合数学计算每个位置选择特定字符后的排列数量
算法步骤：
- 统计字符频率，计算前半部分长度
len = n/2 - 对于前半部分的每个位置，从小到大尝试每个可用字符
- 计算选择当前字符后剩余位置的排列数（使用多项式系数）
- 如果排列数 ≥ k，选择该字符；否则减去排列数继续尝试下一个字符
- 构造完前半部分后，利用对称性生成完整回文
组合数学关键：
使用多项式系数计算排列数：n! / (c1! × c2! × ... × cm!)，其中 ci 是字符 i 的剩余数量。
时间复杂度主要在于计算阶乘和组合数，需要预处理阶乘表以优化性能。
代码实现
class Solution {
public:
string smallestPalindrome(string s, int k) {
int n = s.length();
vector<int> count(26, 0);
for (char c : s) {
count[c - 'a']++;
}
// Use half counts for front half
for (int i = 0; i < 26; i++) {
count[i] /= 2;
}
int len = n / 2;
// Precompute factorials
vector<long long> fact(len + 1);
fact[0] = 1;
for (int i = 1; i <= len; i++) {
fact[i] = fact[i - 1] * i;
}
string front = "";
for (int pos = 0; pos < len; pos++) {
bool found = false;
for (int ch = 0; ch < 26; ch++) {
if (count[ch] == 0) continue;
count[ch]--;
int remaining = len - pos - 1;
// Calculate multinomial coefficient
long long ways = fact[remaining];
for (int i = 0; i < 26; i++) {
for (int j = 0; j < count[i]; j++) {
ways /= (j + 1);
}
}
if (ways >= k) {
front += (char)('a' + ch);
found = true;
break;
} else {
k -= ways;
count[ch]++;
}
}
if (!found) return "";
}
string back = front;
reverse(back.begin(), back.end());
if (n % 2 == 1) {
// Find the middle character
for (int i = 0; i < 26; i++) {
if (count[i] > 0) {
front += (char)('a' + i);
break;
}
}
}
return front + back;
}
};
class Solution:
def smallestPalindrome(self, s: str, k: int) -> str:
from collections import Counter
import math
n = len(s)
count = Counter(s)
# Use half counts for front half
for ch in count:
count[ch] //= 2
length = n // 2
# Precompute factorials
fact = [1] * (length + 1)
for i in range(1, length + 1):
fact[i] = fact[i - 1] * i
front = ""
for pos in range(length):
found = False
for ch in sorted(count.keys()):
if count[ch] == 0:
continue
count[ch] -= 1
remaining = length - pos - 1
# Calculate multinomial coefficient
ways = fact[remaining]
for cnt in count.values():
ways //= math.factorial(cnt)
if ways >= k:
front += ch
found = True
break
else:
k -= ways
count[ch] += 1
if not found:
return ""
back = front[::-1]
if n % 2 == 1:
# Find the middle character
for ch in sorted(count.keys()):
if count[ch] > 0:
front += ch
break
return front + back
public class Solution {
public string SmallestPalindrome(string s, int k) {
int n = s.Length;
int[] count = new int[26];
foreach (char c in s) {
count[c - 'a']++;
}
// Use half counts for front half
for (int i = 0; i < 26; i++) {
count[i] /= 2;
}
int len = n / 2;
// Precompute factorials
long[] fact = new long[len + 1];
fact[0] = 1;
for (int i = 1; i <= len; i++) {
fact[i] = fact[i - 1] * i;
}
string front = "";
for (int pos = 0; pos < len; pos++) {
bool found = false;
for (int ch = 0; ch < 26; ch++) {
if (count[ch] == 0) continue;
count[ch]--;
int remaining = len - pos - 1;
// Calculate multinomial coefficient
long ways = fact[remaining];
for (int i = 0; i < 26; i++) {
for (int j = 0; j < count[i]; j++) {
ways /= (j + 1);
}
}
if (ways >= k) {
front += (char)('a' + ch);
found = true;
break;
} else {
k -= (int)ways;
count[ch]++;
}
}
if (!found) return "";
}
char[] backArray = front.ToCharArray();
Array.Reverse(backArray);
string back = new string(backArray);
if (n % 2 == 1) {
// Find the middle character
for (int i = 0; i < 26; i++) {
if (count[i] > 0) {
front += (char)('a' + i);
break;
}
}
}
return front + back;
}
}
var smallestPalindrome = function(s, k) {
const n = s.length;
const freq = {};
// Count frequency of each character
for (let char of s) {
freq[char] = (freq[char] || 0) + 1;
}
// Get characters that appear in pairs and the middle character (if any)
const pairs = [];
let middle = '';
for (let char of Object.keys(freq).sort()) {
const count = freq[char];
for (let i = 0; i < Math.floor(count / 2); i++) {
pairs.push(char);
}
if (count % 2 === 1) {
middle = char;
}
}
// Calculate total number of palindromic permutations
const factorial = (num) => {
let result = 1n;
for (let i = 2; i <= num; i++) {
result *= BigInt(i);
}
return result;
};
let total = factorial(pairs.length);
const charCount = {};
for (let char of pairs) {
charCount[char] = (charCount[char] || 0) + 1;
}
for (let count of Object.values(charCount)) {
total /= factorial(count);
}
if (BigInt(k) > total) {
return "";
}
// Generate the k-th permutation of the first half
const result = [];
const available = [...pairs];
let remaining = BigInt(k - 1);
while (available.length > 0) {
// Count frequency of remaining characters
const remainingFreq = {};
for (let char of available) {
remainingFreq[char] = (remainingFreq[char] || 0) + 1;
}
const uniqueChars = Object.keys(remainingFreq).sort();
for (let char of uniqueChars) {
// Calculate permutations if we choose this character
const tempAvailable = available.slice();
const idx = tempAvailable.indexOf(char);
tempAvailable.splice(idx, 1);
let perms = factorial(tempAvailable.length);
const tempCharCount = {};
for (let c of tempAvailable) {
tempCharCount[c] = (tempCharCount[c] || 0) + 1;
}
for (let count of Object.values(tempCharCount)) {
perms /= factorial(count);
}
if (remaining < perms) {
result.push(char);
available.splice(idx, 1);
break;
}
remaining -= perms;
}
}
// Build the palindrome
const firstHalf = result.join('');
const secondHalf = result.slice().reverse().join('');
return firstHalf + middle + secondHalf;
};
复杂度分析
| 复杂度类型 | 值 |
|---|---|
| 时间复杂度 | O(n² × 26) |
| 空间复杂度 | O(n) |
其中 n 是字符串长度。时间复杂度主要来源于每个位置计算多项式系数的过程。