A palindrome is pinned down entirely by its first half, so ranking the palindromic rearrangements of `s` is the same task as ranking the distinct permutations of that half — and the k-th one can be built letter by letter without ever listing a candidate. The naive instinct is to generate every palindrome, drop them into a set to dedupe, sort, and index to `k`. That dies on the constraints: with `s.length` up to `10^4` the number of arrangements dwarfs the `k <= 10^6` you actually care about, so enumeration never finishes. Because `s` is already a palindrome, at most one letter has an odd count — that letter is the fixed middle, and every other letter contributes `count/2` copies to the first half. Two palindromes compare in the same order as their first halves, since the mirrored tail and the shared middle never decide the tie first, so I only ever rank first halves. ### Worked example Take `s = "abba"`, `k = 2`. The half multiset is `{a:1, b:1}`, no middle. At position 0 I try `a`: fixing it leaves `{b:1}` with `1` arrangement. Since `k = 2 > 1`, everything starting with `a` sorts first, so I subtract — `k` becomes `1` — and move on. I try `b`: fixing it leaves `{a:1}` with `1` arrangement and `1 <= 1`, so `b` stays. Position 1 places the leftover `a`. First half `ba` -> palindrome `ba` + `ab` = `baab`. ### Complexity - Time O(n^2) — `n/2` positions, each trying up to 26 letters, and each trial recomputes the capped permutation count in O(n/2); the alphabet size is a constant factor. - Space O(n) — only the 26-entry count arrays plus the output string. ### Code (C++) ```cpp class Solution { public: string smallestPalindrome(string s, int k) { vector cnt(26, 0); for (char c : s) cnt[c - 'a']++; vector half(26, 0); int mid = -1; for (int i = 0; i < 26; i++) { if (cnt[i] % 2 == 1) mid = i; half[i] = cnt[i] / 2; } const long long CAP = 2000000LL; // > max k (1e6) auto countPerms = [&](vector& c) -> long long { long long result = 1, filled = 0; for (int ch = 0; ch < 26; ch++) { for (long long i = 1; i <= c[ch]; i++) { filled++; result = result * filled / i; if (result > CAP) return CAP; } } return result; }; long long total = countPerms(half); if ((long long)k > total) return ""; int H = 0; for (int i = 0; i < 26; i++) H += half[i]; string firstHalf; for (int pos = 0; pos < H; pos++) { for (int ch = 0; ch < 26; ch++) { if (half[ch] == 0) continue; half[ch]--; long long p = countPerms(half); if ((long long)k <= p) { firstHalf.push_back('a' + ch); break; } else { k -= (int)p; half[ch]++; } } } string res = firstHalf; if (mid >= 0) res.push_back('a' + mid); for (int i = (int)firstHalf.size() - 1; i >= 0; i--) res.push_back(firstHalf[i]); return res; } }; ``` ### One note The permutation count of a `5000`-letter half is astronomically larger than any 64-bit integer can hold, but `k` never exceeds `10^6`, so I clamp `countPerms` the moment it crosses `CAP = 2*10^6` and return that sentinel. The single guard does two jobs: it stops `result * filled` from overflowing (the running product stays below about `CAP * n`), and it preserves every comparison that matters — a count reported as `CAP` means `more than enough`, which is exactly what a `k <= p` test needs. When the answer space is huge but the query index is small, cap the count instead of computing it exactly.