Description
You are given a palindromic string s and an integer k.
Return the k-th lexicographically smallest palindromic permutation of s. If there are fewer than k distinct palindromic permutations, return an empty string.
Note: Different rearrangements that yield the same palindromic string are considered identical and are counted once.
Example 1:
Input: s = "abba", k = 2
Output: "baab"
Explanation:
- The two distinct palindromic rearrangements of
"abba"are"abba"and"baab". - Lexicographically,
"abba"comes before"baab". Sincek = 2, the output is"baab".
Example 2:
Input: s = "aa", k = 2
Output: ""
Explanation:
- There is only one palindromic rearrangement:
"aa". - The output is an empty string since
k = 2exceeds the number of possible rearrangements.
Example 3:
Input: s = "bacab", k = 1
Output: "abcba"
Explanation:
- The two distinct palindromic rearrangements of
"bacab"are"abcba"and"bacab". - Lexicographically,
"abcba"comes before"bacab". Sincek = 1, the output is"abcba".
Constraints:
1 <= s.length <= 104sconsists of lowercase English letters.sis guaranteed to be palindromic.1 <= k <= 106
Solutions
This is an optimized version that finds the k-th smallest palindrome directly using combinatorics instead of generating every palindrome: it counts letter frequencies in the first half of s, then for each position builds the answer character by character, using a C (combination/multinomial count) helper to calculate how many palindromes would result from placing each candidate letter (in alphabetical order) — if that count is large enough to reach the target k, it commits to that letter and moves on, otherwise it skips ahead by that count and tries the next letter; this lets it "jump" straight to the correct answer without enumerating all permutations, making it dramatically faster and avoiding the TLE from the previous approach.
/**
* @param {string} s
* @param {number} k
* @return {string}
*/
var smallestPalindrome = function (s, k) {
const C = (n, m, kLimit) => {
let res = 1;
m = Math.min(m, n - m);
for (let i = 1; i <= m; i++) {
res = (res * (n - i + 1)) / i;
if (res > kLimit) {
return kLimit + 1;
}
}
return res;
};
const partition = Math.floor(s.length / 2);
const bucket = new Int32Array(26);
for (let i = 0; i < partition; i++) {
bucket[s.charCodeAt(i) - 97] += 1;
}
const permutations = (rem) => {
let ways = 1;
for (let i = 0; i < 26; i++) {
if (bucket[i] === 0) {
continue;
}
ways *= C(rem, bucket[i], k);
if (ways > k) {
break;
}
rem -= bucket[i];
}
return ways;
};
let left = "";
let startIndex = 1;
for (let pos = 0; pos < partition; pos++) {
for (let i = 0; i < 26; i++) {
if (bucket[i] === 0) {
continue;
}
bucket[i] -= 1;
const ways = permutations(partition - pos - 1);
if (startIndex + ways > k) {
left += String.fromCharCode(i + 97);
break;
}
bucket[i] += 1;
startIndex += ways;
}
}
if (left.length < partition) {
return "";
}
const mid = s.length % 2 !== 0 ? s[partition] : "";
const right = left.split("").reverse().join("");
return left + mid + right;
};