#include <stdlib.h>
#include <string.h>

// 演算法 / Algorithm:
// 回文由左半邊決定；只構造 n/2 個字元。從左到右、字母由小到大貪心，
// 每步用「多重集合排列數」數出剩餘排列數，決定第 k 個落在哪個字母。
// A palindrome is fixed by its left half; build only n/2 chars. Greedily pick
// each position (smallest letter first), using multinomial counts to locate the k-th.

// 計算 r!/∏cnt[c]!（r = cnt 總和），一超過 cap 就封頂回傳 cap+1。
// Compute r!/∏cnt[c]! (r = sum of cnt), clamped to cap+1 once it exceeds cap.
static long long multinomial(int *cnt, long long cap) {
    long long perm = 1;   // 目前的排列數 / running permutation count
    long long used = 0;   // 已放入的字元總數 / how many items placed so far
    for (int c = 0; c < 26; c++) {           // 掃過每個字母 / for each letter
        for (int j = 1; j <= cnt[c]; j++) {  // 逐一加入該字母 / add its copies one by one
            used++;                          // 多放一個字元 / one more item placed
            // perm * used / j 逐步搭出組合數，每步都是整數，不會有分數。
            // perm * used / j builds binomial products; each step stays an exact integer.
            perm = perm * used / j;
            if (perm > cap) return cap + 1;  // 太大就封頂 / clamp when it grows past cap
        }
    }
    return perm;                             // 未超過 cap 的精確值 / exact value under cap
}

// LeetCode 函式簽名 / LeetCode signature
char* smallestPalindrome(char* s, int k) {
    int n = strlen(s);                       // 字串長度 / length of s
    int cnt[26] = {0};                       // 每個字母出現次數 / frequency of each letter
    for (int i = 0; i < n; i++) cnt[s[i] - 'a']++;  // s[i]-'a' 把字母映成 0..25 / map letter to index

    int half[26];                            // 左半邊可用次數 / usable counts for the left half
    int oddChar = -1;                        // 出現奇數次的字母（中間） / the odd-count letter (middle)
    for (int c = 0; c < 26; c++) {
        if (cnt[c] & 1) oddChar = c;         // &1 判斷是否為奇數 / bitwise test for oddness
        half[c] = cnt[c] / 2;                // 半數字元 / half of each count
    }
    int h = n / 2;                           // 左半邊長度 / length of the left half
    long long cap = 1000000;                 // k <= 1e6，封頂上限 / cap since k <= 1e6

    char *res = malloc(n + 1);               // 配置輸出空間，+1 給結尾 '\0' / output buffer, +1 for terminator
    // 若左半邊的排列總數都不足 k，回傳空字串。
    // If even the total number of half-arrangements is below k, return "".
    if (multinomial(half, cap) < k) { res[0] = '\0'; return res; }

    // 逐位構造左半邊 / build the left half position by position
    for (int pos = 0; pos < h; pos++) {
        for (int c = 0; c < 26; c++) {       // 由小到大試字母 / try letters smallest first
            if (half[c] == 0) continue;      // 沒有這個字母就跳過 / skip exhausted letters
            half[c]--;                       // 試著把 c 放這一位 / tentatively place c here
            long long ways = multinomial(half, cap);  // 剩餘位置的排列數 / arrangements of the rest
            if (ways >= k) {                 // 第 k 個就在此分支 / the k-th falls in this branch
                res[pos] = 'a' + c;          // 固定字母 c，保持 half[c] 已減 / commit c (keep the decrement)
                break;
            }
            k -= ways;                        // 跳過此分支的 ways 個 / skip these ways arrangements
            half[c]++;                        // 還原，換更大的字母 / undo and try a larger letter
        }
    }

    int mid = h;                             // 中間字元的位置 / index of the middle slot
    if (oddChar >= 0) { res[mid] = 'a' + oddChar; mid++; }  // 有奇數字元就放中間 / place middle if it exists
    for (int i = 0; i < h; i++)              // 右半邊 = 左半邊的鏡像 / right half mirrors the left
        res[mid + i] = res[h - 1 - i];
    res[n] = '\0';                           // C 字串結尾符 / null terminator ends the C string
    return res;
}