Kth Distinct Palindromic Rearrangement
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
You are given a lowercase English palindrome `s` and a positive integer `k`. Consider all **distinct** palindromic strings formed by rearranging exactly the characters of `s`, preserving their multiplicities.
Return the `k`-th string in increasing lexicographic order, with rank `1` meaning the smallest string. If fewer than `k` distinct palindromic rearrangements exist, return an empty string `""`.
Different choices of identical character copies that produce the same string count only once.
### C++ Interface
```cpp
class Solution {
public:
string smallestPalindrome(string s, int k) {
}
};
```
### Examples
**Example 1**
```text
Input: s = "cbaabc", k = 4
Output: "bcaacb"
```
The distinct palindromes in order are `abccba`, `acbbca`, `baccab`, `bcaacb`, `cabbac`, and `cbaabc`. The fourth is `bcaacb`.
**Example 2**
```text
Input: s = "aabaa", k = 2
Output: ""
```
There is only one distinct palindromic rearrangement, `aabaa`. Permuting its identical `a` copies does not create another string, so rank two does not exist.
### Constraints
- `1 <= s.length <= 10000`.
- `s` contains only lowercase English letters.
- `s` is guaranteed to be palindromic.
- `1 <= k <= 1000000`.
### Clarifying Questions
- Is `k` zero-based? No. The smallest distinct palindrome has rank `1`.
- Are the available letters chosen independently of `s`? No. Use exactly its character multiset.
- Can the empty-string result mean a valid empty rearrangement? No. The input is nonempty; `""` indicates that the requested rank does not exist.
### What a Strong Answer Covers
- The palindrome requirement, character multiplicities, and distinct-string ranking.
- The exact one-based rank and empty result when that rank is unavailable.
- Odd and even lengths, repeated letters, and a single-character input.
- Correct arithmetic and resource bounds for the full length and rank limits.
### Follow-up Questions
- How would counting arrangements of individually labeled identical copies change the meaning of a rank?
- What result should be returned when there is only one distinct palindromic rearrangement and `k` is greater than one?
```hint Count completions of a prefix
Only one half of a palindrome is free to vary. Try its next letter in lexicographic order and count distinct completions of the remaining multiset. Counts need only be exact below the current rank; when a count reaches that rank, it can safely be capped there.
```
Overview: Find the one-based kth distinct palindromic rearrangement of a lowercase palindrome. Preserve character multiplicities, exact lexicographic ranking and the empty result for an unavailable rank.