3518. Smallest Palindromic Rearrangement II

題目 / Problem

中文： 給你一個回文字串 s（正著讀和反著讀一樣）和一個整數 k。請回傳把 s 的字元重新排列後、仍然是回文的所有字串中，字典序第 k 小的那一個。如果不同的回文排列少於 k 個，回傳空字串 ""。注意：不同的重排若拼出同一個字串，只算一次。

English: You are given a palindromic string s (reads the same forwards and backwards) and an integer k. Return the k-th lexicographically smallest string that is a palindrome and uses exactly the same multiset of characters as s. If there are fewer than k distinct palindromic permutations, return "". Rearrangements that produce the same string are counted once.

Constraints: - 1 <= s.length <= 10^4 - s consists of lowercase English letters - s is guaranteed to be palindromic - 1 <= k <= 10^6

Worked example: s = "abba", k = 2. The two distinct palindromes are "abba" and "baab". In lexicographic order that's abba (1st) then baab (2nd). Since k = 2, the answer is "baab".

名詞解釋 / Glossary

回文 / Palindrome: A string equal to its own reverse, e.g. abcba. A palindrome is fully determined by its left half plus an optional single middle character.
字典序 / Lexicographic order: Dictionary order — compare character by character from the left; "aab" < "aba" because at the first differing position a < b.
排列 / Permutation: An arrangement of the given characters. "Distinct permutations" means we ignore identical results (swapping two equal letters changes nothing).
字元計數 / Frequency count: An array cnt[26] where cnt[c] is how many times letter c appears. Built by scanning the string once.
多重集合排列數 / Multinomial coefficient: The number of distinct orderings of a multiset of length r with group sizes c_1,…,c_m is r! / (c_1!·c_2!·…·c_m!). This counts palindrome halves for us.
封頂 / Capping (clamping): These counts can be astronomically large, but k ≤ 10^6. So whenever a running count exceeds 10^6 we just clamp it to 10^6 + 1 ("big enough"). This keeps every number inside a 64-bit integer.
貪心逐位構造 / Greedy digit-by-digit construction: Instead of listing all palindromes, we decide each position from left to right, always trying the smallest letter first and counting how many palindromes that choice would allow.

思路

中文： 最直接的想法是列出所有回文排列、排序、取第 k 個。但長度可到 10^4，回文數量是天文數字，完全不可行。關鍵觀察有兩點。第一，回文只由左半邊決定：右半邊是左半邊的鏡像，中間最多一個字元（出現奇數次的那個，因為 s 保證是回文，這種字元最多一個）。所以我們只需構造 floor(n/2) 個字元，每個字元可用的次數是 cnt[c] / 2。這樣「第 k 小的回文」就等價於「用這些半數字元、第 k 小的排列」。第二，要找第 k 小的排列，不必真的列舉：從最左位置開始，按字母 a 到 z 嘗試，假設這一位放字元 c，剩下的位置能組成的排列數就是一個多重集合排列數 r!/∏cnt!。若這個數量 ≥ k，代表第 k 個就落在「這一位是 c」的區間裡，於是固定 c；否則把 k 減掉這個數量，換下一個更大的字母。因為我們按字母由小到大掃，第一個滿足 ≥ k 的就是正確選擇。由於 k ≤ 10^6，計算排列數時只要一超過 10^6 就封頂成 10^6+1，所有數值都能安全放進 64 位整數，不會溢位。開始前先算左半邊的總排列數，若小於 k 直接回傳空字串。

English: The brute force — enumerate every palindromic permutation, sort, take the k-th — is hopeless because with length up to 10^4 the count is enormous. Two observations unlock the problem. First, a palindrome is determined entirely by its left half: the right half is the mirror, and there is at most one middle character (the one appearing an odd number of times; since s is guaranteed palindromic there is at most one such character). So we only need to build floor(n/2) characters, where each letter c is available cnt[c] / 2 times. Finding the k-th smallest palindrome is exactly finding the k-th smallest arrangement of this half-multiset. Second, we never enumerate: we build the half left to right. At each position we try letters a…z; if we tentatively place letter c, the number of ways to fill the remaining positions is the multinomial r!/∏cnt!. If that count is ≥ k, the k-th arrangement starts with c, so we fix it; otherwise we subtract the count from k and move to the next larger letter. Scanning smallest-first guarantees the first letter that satisfies ≥ k is the correct one. Because k ≤ 10^6, we cap every count at 10^6 + 1 the moment it exceeds 10^6, keeping all arithmetic safely inside 64-bit integers. Before building, we compute the total number of half-arrangements; if it is below k, we immediately return the empty string.

逐步走查 / Walkthrough

Input s = "abba", k = 2. Counts: a:2, b:2. Half counts half = {a:1, b:1}, no odd character, half length h = 2. Total half-arrangements = 2!/(1!·1!) = 2 ≥ k, so an answer exists.

Step / 步驟	Position	Try letter	`half` before try	ways = perms of the rest	Decision / 決定	k after
1	pos 0	`a`	`{a:1,b:1}`	place `a` → `{a:0,b:1}` → `1!/(1!) = 1`	`1 ≥ 2`? No → `k -= 1`, undo	1
2	pos 0	`b`	`{a:1,b:1}`	place `b` → `{a:1,b:0}` → `1!/(1!) = 1`	`1 ≥ 1`? Yes → fix `b`	1
3	pos 1	`a`	`{a:1,b:0}`	place `a` → `{}` → `0! = 1`	`1 ≥ 1`? Yes → fix `a`	1

Left half built = "ba". No middle character. Right half = reverse of left = "ab". Full palindrome = "ba" + "ab" = "baab". ✅ Matches the expected output.

Solution — C

#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 給結尾 '' / 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] = ''; 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] = '';                           // C 字串結尾符 / null terminator ends the C string
    return res;
}

Solution — C++

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

// 演算法同 C 版：只構造左半邊，貪心逐位，用多重集合排列數定位第 k 個。
// Same as the C version: build only the left half, greedy per position,
// using multinomial counts (capped) to locate the k-th arrangement.
class Solution {
    // 計算 r!/∏cnt!，超過 cap 就封頂 / multinomial r!/∏cnt!, clamped at cap
    long long multinomial(vector<int>& cnt, long long cap) {
        long long perm = 1, used = 0;        // perm 排列數, used 已放入數 / running count and items placed
        for (int c = 0; c < 26; c++)
            for (int j = 1; j <= cnt[c]; j++) {
                used++;                      // 多放一個字元 / one more item
                perm = perm * used / j;      // 逐步搭出組合數（保持整數） / build binomials, stays integer
                if (perm > cap) return cap + 1;  // 封頂避免溢位 / clamp to avoid overflow
            }
        return perm;
    }
public:
    string smallestPalindrome(string s, int k) {
        int n = s.size();
        vector<int> cnt(26, 0);              // vector 是可變長度陣列 / vector is a growable array
        for (char ch : s) cnt[ch - 'a']++;   // range-for 走訪每個字元 / range-for over each char

        vector<int> half(26);                // 左半邊可用次數 / usable half counts
        int oddChar = -1;                    // 中間字元 / the middle (odd-count) letter
        for (int c = 0; c < 26; c++) {
            if (cnt[c] & 1) oddChar = c;     // 判斷奇偶 / test oddness
            half[c] = cnt[c] / 2;            // 取一半 / take half
        }
        int h = n / 2;                       // 左半邊長度 / left-half length
        long long cap = 1000000;             // k <= 1e6 的封頂 / cap for k <= 1e6

        // 總排列數不足 k 就回空字串 / not enough distinct palindromes → ""
        if (multinomial(half, cap) < k) return "";

        string first(h, ' ');                // 左半邊字串，先填佔位 / left half, placeholder-filled
        for (int pos = 0; pos < h; pos++) {
            for (int c = 0; c < 26; c++) {   // 由小到大試字母 / smallest letter first
                if (half[c] == 0) continue;  // 用完就跳過 / skip exhausted letters
                half[c]--;                   // 試放 c / tentatively place c
                long long ways = multinomial(half, cap);  // 剩餘排列數 / arrangements of remainder
                if (ways >= k) {             // 第 k 個在此分支 / the k-th is here
                    first[pos] = 'a' + c;    // 固定 c / commit c
                    break;
                }
                k -= ways;                   // 跳過此分支 / skip this branch's ways
                half[c]++;                   // 還原 / undo
            }
        }

        string res = first;                          // 左半邊 / left half
        if (oddChar >= 0) res += char('a' + oddChar);// 有奇數字元放中間 / middle char if present
        // string(rbegin, rend) 是反轉字串 / reversed copy via reverse iterators
        res += string(first.rbegin(), first.rend()); // 右半邊為左半鏡像 / right half mirrors left
        return res;
    }
};

複雜度 / Complexity

Time: O(n² · |Σ|) worst case, with |Σ| = 26 a constant, so effectively O(n²). Here n is the string length and the half has length h = n/2. For each of the h positions we try up to 26 letters, and each multinomial call scans the half in O(h). In practice the capping makes each count reach 10^6+1 and exit early, so it runs far faster than the worst bound. / 每個位置嘗試至多 26 個字母，每次數排列數為 O(h)，封頂讓多數情況提早結束。
Space: O(n) — the output string of length n, plus fixed-size cnt and half arrays of 26 ints (constant). / 輸出字串 O(n)，加上兩個大小固定為 26 的陣列。

Pitfalls & Edge Cases

數值溢位 / Overflow: The true permutation counts explode far beyond 64-bit range. Because k ≤ 10^6, we clamp any count above 10^6 to 10^6+1. In multinomial, perm ≤ 10^6+1 and used ≤ n/2 ≤ 5000, so perm * used stays under ~5·10^9, safely inside long long. / 排列數極大，一律封頂在 10^6+1，中間乘積不會溢位。
整數除法順序 / Integer-division order: Writing perm = perm * used / j (multiply then divide) matters. Each partial product perm * used is divisible by j because it builds a binomial coefficient; dividing first would truncate and give wrong counts. / 必須先乘後除，否則整數除法會截斷出錯。
少於 k 個時回傳空字串 / Fewer than k arrangements: Always check the total half-count against k first; forgetting this makes the greedy loop consume all letters yet still be "short," producing garbage instead of "". / 先檢查總數是否 < k，否則會產生錯誤結果而非空字串。
中間字元 / The middle character: For odd n exactly one letter has an odd count; it must sit in the center and is not part of the freely-arranged half. Since s is guaranteed palindromic, at most one such letter exists — no need to validate feasibility. / 奇數長度時唯一奇數次字元固定放中間，不參與左半排列。
邊界 n = 1 / Single character: h = 0, the build loop doesn't run, and the answer is just the middle character (valid only when k = 1). The total-count check handles k > 1 by returning "". / 長度 1 時只有中間字元，k>1 由總數檢查擋掉。
貪心方向 / Greedy direction: Letters must be tried from a to z. Trying largest-first would find the k-th largest, not smallest. / 必須由小到大掃，才是字典序第 k 小。