# Smallest Palindromic Rearrangement II
**Difficulty:** HARD
[External](https://leetcode.com/problems/smallest-palindromic-rearrangement-ii)
Canonical: https://scaleengineer.com/dsa/problems/smallest-palindromic-rearrangement-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
---
## Problem
You are given a **palindromic** string `s` and an integer `k`.

Return the **k-th** **lexicographically smallest** palindromic permutation of `s`. If there are fewer than `k` distinct palindromic permutations, return an empty string.

**Note:** Different rearrangements that yield the same palindromic string are considered identical and are counted once.

**Example 1:**

**Input:** s = "abba", k = 2

**Output:** "baab"

**Explanation:**

* The two distinct palindromic rearrangements of `"abba"` are `"abba"` and `"baab"`.
* Lexicographically, `"abba"` comes before `"baab"`. Since `k = 2`, the output is `"baab"`.

**Example 2:**

**Input:** s = "aa", k = 2

**Output:** ""

**Explanation:**

* There is only one palindromic rearrangement: `"aa"`.
* The output is an empty string since `k = 2` exceeds the number of possible rearrangements.

**Example 3:**

**Input:** s = "bacab", k = 1

**Output:** "abcba"

**Explanation:**

* The two distinct palindromic rearrangements of `"bacab"` are `"abcba"` and `"bacab"`.
* Lexicographically, `"abcba"` comes before `"bacab"`. Since `k = 1`, the output is `"abcba"`.

**Constraints:**

* `1 <= s.length <= 104`
* `s` consists of lowercase English letters.
* `s` is guaranteed to be palindromic.
* `1 <= k <= 106`

# Approaches
## Brute-force Generation and Sorting
This approach is a straightforward brute-force method. The core idea is that any palindromic rearrangement is defined by the first half of the string. We first determine the characters that make up this first half (for `"abba"`, it's `"ab"`; for `"bacab"`, it's `"ab"`). Then, we generate every possible unique arrangement (permutation) of this half-string. After generating all of them, we sort them lexicographically and pick the k-th one. Finally, we construct the full palindrome from this k-th half-string.
**Time:** O(P * L + P log P), where `P` is the number of unique permutations of the half-string and `L` is its length. Generating all permutations is the dominant factor. For a half-string of length `L` with distinct characters, `P` would be `L!`, which grows extremely fast. · **Space:** O(P * L), where `P` is the number of unique permutations and `L` is the length of the half-string. This is because we need to store all `P` permutations, each of length `L`.
**Pros:** Conceptually simple and easy to follow.
**Cons:** Extremely high time complexity, making it infeasible for the given constraints.; High space complexity due to storing all permutations.
### Explanation
The algorithm begins by analyzing the character composition of the input string `s`. Since `s` is a palindrome, each character appears an even number of times, with at most one character appearing an odd number of times. This odd-count character will be the center of any new palindrome.

The characters for the first half of the new palindrome are determined by taking half of the count of each character. For example, if `s = "aabbaa"`, the half-string will be composed of three 'a's and one 'b'.

We then use a standard backtracking algorithm to find all unique permutations of this half-string. A frequency map (or an array) is used to keep track of available characters to avoid duplicates in the generation process.

Once all unique permutations are generated and stored, the list is sorted. If the list size is less than `k`, we return `""`. Otherwise, we select the `(k-1)`-th element. This element, combined with the middle character and its own reverse, forms the desired k-th smallest palindromic permutation.

```java
import java.util.*;

class Solution {
    List<String> permutations = new ArrayList<>();
    
    public String kthSmallestPalindrome(String s, int k) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }

        String mid = "";
        StringBuilder half = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (counts[i] % 2 != 0) {
                mid += (char) ('a' + i);
            }
            for (int j = 0; j < counts[i] / 2; j++) {
                half.append((char) ('a' + i));
            }
        }

        int[] halfCounts = new int[26];
        for(char c : half.toString().toCharArray()) {
            halfCounts[c - 'a']++;
        }

        generatePermutations(new StringBuilder(), half.length(), halfCounts);

        Collections.sort(permutations);

        if (k > permutations.size()) {
            return "";
        }

        String halfPerm = permutations.get(k - 1);
        String reversedHalf = new StringBuilder(halfPerm).reverse().toString();
        return halfPerm + mid + reversedHalf;
    }

    private void generatePermutations(StringBuilder current, int len, int[] counts) {
        if (current.length() == len) {
            permutations.add(current.toString());
            return;
        }

        for (int i = 0; i < 26; i++) {
            if (counts[i] > 0) {
                counts[i]--;
                current.append((char) ('a' + i));
                generatePermutations(current, len, counts);
                current.deleteCharAt(current.length() - 1);
                counts[i]++;
            }
        }
    }
}
```
### Algorithm
1. **Count Character Frequencies:** Traverse the input string `s` to count the occurrences of each character.
2. **Form Half-String and Middle Character:** Based on the counts, construct the 'half-string'. For each character `c` with count `n`, the half-string will contain `n / 2` instances of `c`. If there's a character with an odd count, that will be the middle character of the palindrome.
3. **Generate All Permutations:** Use a recursive backtracking algorithm to generate all unique permutations of the half-string.
4. **Store and Sort:** Store all generated unique permutations in a list.
5. **Sort Lexicographically:** Sort the list of permutations in lexicographical order.
6. **Select k-th Permutation:** If `k` is larger than the number of unique permutations, it's impossible to find the k-th one, so return an empty string. Otherwise, retrieve the permutation at index `k-1` from the sorted list.
7. **Construct Final Palindrome:** Take the selected half-string permutation, append the middle character (if any), and then append the reverse of the half-string permutation to form the final palindromic string.

## Direct Mathematical Construction
This efficient approach avoids generating all permutations by directly constructing the k-th one mathematically. It builds the permutation of the half-string from left to right. At each position, it determines which character should be placed by calculating how many permutations would follow if we chose a particular character. By comparing this count with the current value of `k`, it decides whether to pick that character or to skip that block of permutations and try the next character.
**Time:** The worst-case complexity appears to be O(d * L^2), where `d` is the alphabet size and `L` is the half-string length. However, because `k` is small (`<= 10^6`), the permutation counts calculated in each step quickly exceed `k`. This causes the `countPerms` function to return early. The practical time complexity is much better, closer to O(d^2 * L), which is efficient enough for the given constraints. · **Space:** O(L^2) for precomputing combinations, where `L` is the half-string length. If not precomputed, space is O(d) or O(1) for character counts, where `d` is the alphabet size (26).
**Pros:** Highly efficient, capable of handling large inputs within typical time limits.; Constant space complexity (relative to input size), as it doesn't store large intermediate structures.
**Cons:** More complex to implement due to the need for combinatorial calculations.; Requires careful handling of large numbers, even with capping, to prevent overflow and precision issues.
### Explanation
The algorithm leverages a standard technique for finding the k-th lexicographical permutation of a multiset. First, we process the input string `s` to get the character counts for the first half of the palindrome (`half_counts`) and the potential middle character.

The crucial part is a helper function that can calculate the number of permutations for a given set of character counts. This is calculated using multinomial coefficients: `n! / (c1! * c2! * ...)` where `n` is the total number of items and `ci` are the counts of each unique item. To handle potentially huge numbers and to optimize, this calculation is capped at `k`, as any count larger than `k` is equivalent for our decision-making process.

We initialize `k` to `k-1` for 0-based indexing. Then, we determine the first character of our target permutation. We try the smallest character, 'a'. We calculate how many permutations start with 'a'. If this count is greater than `k`, we know our target permutation must also start with 'a'. If the count is less than or equal to `k`, we subtract this count from `k` and try the next character, 'b'. This process is repeated for each position in the half-string, progressively narrowing down `k` and building the result. The small value of `k` is a key constraint that makes this approach very fast in practice, as the number of permutations of the remaining string quickly exceeds `k`, meaning for most of the initial positions, we will simply pick the lexicographically smallest available character.

```java
import java.util.Arrays;

class Solution {
    long[][] C;

    public String kthSmallestPalindrome(String s, int k) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }

        String mid = "";
        int[] halfCounts = new int[26];
        int halfLen = 0;
        for (int i = 0; i < 26; i++) {
            if (counts[i] % 2 != 0) {
                mid += (char) ('a' + i);
            }
            halfCounts[i] = counts[i] / 2;
            halfLen += halfCounts[i];
        }

        if (halfLen == 0) {
            return k == 1 ? mid : "";
        }

        // Precompute combinations C(n, k) up to halfLen
        // Capped at k to prevent overflow and for efficiency
        C = new long[halfLen + 1][halfLen + 1];
        for (int i = 0; i <= halfLen; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
                if (C[i][j] > k) C[i][j] = k; // Cap at k
            }
        }

        long totalPerms = countPerms(halfCounts, halfLen, k);
        if (totalPerms < k) {
            return "";
        }

        StringBuilder halfPerm = new StringBuilder();
        int currentLen = halfLen;
        long kRem = k;

        for (int i = 0; i < halfLen; i++) {
            for (int j = 0; j < 26; j++) {
                if (halfCounts[j] > 0) {
                    halfCounts[j]--;
                    long perms = countPerms(halfCounts, currentLen - 1, kRem);
                    if (kRem <= perms) {
                        halfPerm.append((char) ('a' + j));
                        currentLen--;
                        break;
                    } else {
                        kRem -= perms;
                        halfCounts[j]++;
                    }
                }
            }
        }

        String reversedHalf = new StringBuilder(halfPerm).reverse().toString();
        return halfPerm.toString() + mid + reversedHalf;
    }

    private long countPerms(int[] counts, int len, long limit) {
        if (len == 0) return 1;
        long res = 1;
        int remLen = len;
        for (int count : counts) {
            if (count > 0) {
                long combinations = C[remLen][count];
                // Check for overflow before multiplication
                if (combinations > 0 && res > limit / combinations) {
                    return limit;
                }
                res *= combinations;
                if (res >= limit) return limit;
                remLen -= count;
            }
        }
        return res;
    }
}
```
### Algorithm
1. **Character Analysis:** Count character frequencies in `s`. Determine the characters for the half-string (`half_counts`) and the middle character (`mid_char`). Let the length of the half-string be `L`.
2. **Permutation Count Function:** Create a helper function, `countPerms(counts, len, limit)`, to calculate the number of unique permutations of a multiset. This function should use combinatorics (`C(n, k)`) and cap the result at `limit` to avoid overflow and for efficiency.
3. **Feasibility Check:** Use `countPerms` to calculate the total number of unique permutations of the half-string. If this total is less than `k`, no solution exists, so return an empty string.
4. **Iterative Construction:** Build the k-th permutation of the half-string, `half_perm`, character by character from left to right (for `i` from 0 to `L-1`).
5. **Character Selection:** For each position `i`, iterate through possible characters `c` from 'a' to 'z'.
6. **Lookahead:** If character `c` is available (its count > 0), tentatively place it at position `i`. Then, calculate how many permutations (`p`) can be formed with the remaining characters using `countPerms`.
7. **Decision:**
   - If `k <= p`, it means the desired permutation lies within this group. Fix `c` as the character for position `i`, append it to `half_perm`, update the character counts, and proceed to the next position (`i+1`).
   - If `k > p`, the desired permutation is not in this group. Skip over these `p` permutations by updating `k = k - p`, and try the next available character for the current position `i`.
8. **Final Assembly:** Once the `half_perm` of length `L` is constructed, create the full palindrome: `half_perm + mid_char + reverse(half_perm)`.