class Solution {
private static final long CAP = 2_000_000L;
public String smallestPalindrome(String s, int k) {
int n = s.length();
int[] count = new int[26];
for (char ch : s.toCharArray()) count[ch - 'a']++;
char midChar = 0;
boolean hasMid = false;
int[] half = new int[26];
int halfLen = 0;
for (int i = 0; i < 26; i++) {
if (count[i] % 2 == 1) {
midChar = (char) ('a' + i);
hasMid = true;
}
half[i] = count[i] / 2;
halfLen += half[i];
}
long kk = k;
long total = countArrangements(half);
if (total < kk) return "";
StringBuilder sb = new StringBuilder();
int[] cur = half.clone();
for (int pos = 0; pos < halfLen; pos++) {
for (int c = 0; c < 26; c++) {
if (cur[c] == 0) continue;
cur[c]--;
long cnt = countArrangements(cur);
if (cnt >= kk) {
sb.append((char) ('a' + c));
break;
} else {
kk -= cnt;
cur[c]++;
}
}
}
String half1 = sb.toString();
StringBuilder result = new StringBuilder();
result.append(half1);
if (hasMid) result.append(midChar);
result.append(new StringBuilder(half1).reverse());
return result.toString();
}
private long countArrangements(int[] cnt) {
long total = 0;
long m = 1;
for (int i = 0; i < 26; i++) {
if (cnt[i] == 0) continue;
long c = combCapped(total + cnt[i], cnt[i]);
m *= c;
if (m > CAP) m = CAP + 1;
total += cnt[i];
}
return m;
}
private long combCapped(long n, long k) {
if (k < 0 || k > n) return 0;
k = Math.min(k, n - k);
long result = 1;
for (long i = 1; i <= k; i++) {
result = result * (n - k + i) / i;
if (result > CAP) return CAP + 1;
}
return result;
}
}
class Solution:
CAP = 2_000_000
def smallestPalindrome(self, s: str, k: int) -> str:
freq = [0] * 26
for ch in s:
freq[ord(ch) - 97] += 1
half = [0] * 26
half_len = 0
middle = ""
for i in range(26):
if freq[i] & 1:
middle = chr(i + 97)
half[i] = freq[i] // 2
half_len += half[i]
if self.count(half) < k:
return ""
ans = []
for _ in range(half_len):
for c in range(26):
if half[c] == 0:
continue
half[c] -= 1
ways = self.count(half)
if ways >= k:
ans.append(chr(c + 97))
break
k -= ways
half[c] += 1
left = "".join(ans)
return left + middle + left[::-1]
def count(self, cnt):
total = 0
ways = 1
for x in cnt:
if x == 0:
continue
ways *= self.comb(total + x, x)
if ways > self.CAP:
return self.CAP + 1
total += x
return ways
def comb(self, n, r):
if r < 0 or r > n:
return 0
r = min(r, n - r)
ans = 1
for i in range(1, r + 1):
ans = ans * (n - r + i) // i
if ans > self.CAP:
return self.CAP + 1
return ans
class Solution {
static constexpr long long CAP = 2000000;
long long comb(long long n, long long k) {
if (k < 0 || k > n) return 0;
k = min(k, n - k);
long long ans = 1;
for (long long i = 1; i <= k; i++) {
ans = ans * (n - k + i) / i;
if (ans > CAP) return CAP + 1;
}
return ans;
}
long long countWays(vector<int>& cnt) {
long long total = 0;
long long ways = 1;
for (int x : cnt) {
if (x == 0) continue;
ways *= comb(total + x, x);
if (ways > CAP) return CAP + 1;
total += x;
}
return ways;
}
public:
string smallestPalindrome(string s, int k) {
vector<int> freq(26, 0);
for (char c : s)
freq[c - 'a']++;
vector<int> half(26, 0);
int halfLen = 0;
string middle = "";
for (int i = 0; i < 26; i++) {
if (freq[i] & 1)
middle = string(1, char('a' + i));
half[i] = freq[i] / 2;
halfLen += half[i];
}
if (countWays(half) < k)
return "";
string left;
for (int pos = 0; pos < halfLen; pos++) {
for (int c = 0; c < 26; c++) {
if (half[c] == 0) continue;
half[c]--;
long long ways = countWays(half);
if (ways >= k) {
left.push_back(char('a' + c));
break;
}
k -= ways;
half[c]++;
}
}
string right = left;
reverse(right.begin(), right.end());
return left + middle + right;
}
};
var smallestPalindrome = function (s, k) {
const CAP = 2000000;
const freq = new Array(26).fill(0);
for (const ch of s)
freq[ch.charCodeAt(0) - 97]++;
const half = new Array(26).fill(0);
let halfLen = 0;
let middle = "";
for (let i = 0; i < 26; i++) {
if (freq[i] & 1)
middle = String.fromCharCode(97 + i);
half[i] = Math.floor(freq[i] / 2);
halfLen += half[i];
}
if (countWays(half) < k)
return "";
const left = [];
for (let pos = 0; pos < halfLen; pos++) {
for (let c = 0; c < 26; c++) {
if (half[c] === 0) continue;
half[c]--;
const ways = countWays(half);
if (ways >= k) {
left.push(String.fromCharCode(97 + c));
break;
}
k -= ways;
half[c]++;
}
}
const l = left.join("");
return l + middle + [...l].reverse().join("");
function countWays(cnt) {
let total = 0;
let ways = 1;
for (const x of cnt) {
if (x === 0) continue;
ways *= comb(total + x, x);
if (ways > CAP)
return CAP + 1;
total += x;
}
return ways;
}
function comb(n, r) {
if (r < 0 || r > n)
return 0;
r = Math.min(r, n - r);
let ans = 1;
for (let i = 1; i <= r; i++) {
ans = Math.floor(ans * (n - r + i) / i);
if (ans > CAP)
return CAP + 1;
}
return ans;
}
};