Smallest Palindromic Rearrangement II

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.

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.

1import java.util.*;2 3class Solution {4    List<String> permutations = new ArrayList<>();5    6    public String kthSmallestPalindrome(String s, int k) {7        int[] counts = new int[26];8        for (char c : s.toCharArray()) {9            counts[c - 'a']++;10        }11 12        String mid = "";13        StringBuilder half = new StringBuilder();14        for (int i = 0; i < 26; i++) {15            if (counts[i] % 2 != 0) {16                mid += (char) ('a' + i);17            }18            for (int j = 0; j < counts[i] / 2; j++) {19                half.append((char) ('a' + i));20            }21        }22 23        int[] halfCounts = new int[26];24        for(char c : half.toString().toCharArray()) {25            halfCounts[c - 'a']++;26        }27 28        generatePermutations(new StringBuilder(), half.length(), halfCounts);29 30        Collections.sort(permutations);31 32        if (k > permutations.size()) {33            return "";34        }35 36        String halfPerm = permutations.get(k - 1);37        String reversedHalf = new StringBuilder(halfPerm).reverse().toString();38        return halfPerm + mid + reversedHalf;39    }40 41    private void generatePermutations(StringBuilder current, int len, int[] counts) {42        if (current.length() == len) {43            permutations.add(current.toString());44            return;45        }46 47        for (int i = 0; i < 26; i++) {48            if (counts[i] > 0) {49                counts[i]--;50                current.append((char) ('a' + i));51                generatePermutations(current, len, counts);52                current.deleteCharAt(current.length() - 1);53                counts[i]++;54            }55        }56    }57}

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).

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.

1import java.util.Arrays;2 3class Solution {4    long[][] C;5 6    public String kthSmallestPalindrome(String s, int k) {7        int[] counts = new int[26];8        for (char c : s.toCharArray()) {9            counts[c - 'a']++;10        }11 12        String mid = "";13        int[] halfCounts = new int[26];14        int halfLen = 0;15        for (int i = 0; i < 26; i++) {16            if (counts[i] % 2 != 0) {17                mid += (char) ('a' + i);18            }19            halfCounts[i] = counts[i] / 2;20            halfLen += halfCounts[i];21        }22 23        if (halfLen == 0) {24            return k == 1 ? mid : "";25        }26 27        // Precompute combinations C(n, k) up to halfLen28        // Capped at k to prevent overflow and for efficiency29        C = new long[halfLen + 1][halfLen + 1];30        for (int i = 0; i <= halfLen; i++) {31            C[i][0] = 1;32            for (int j = 1; j <= i; j++) {33                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];34                if (C[i][j] > k) C[i][j] = k; // Cap at k35            }36        }37 38        long totalPerms = countPerms(halfCounts, halfLen, k);39        if (totalPerms < k) {40            return "";41        }42 43        StringBuilder halfPerm = new StringBuilder();44        int currentLen = halfLen;45        long kRem = k;46 47        for (int i = 0; i < halfLen; i++) {48            for (int j = 0; j < 26; j++) {49                if (halfCounts[j] > 0) {50                    halfCounts[j]--;51                    long perms = countPerms(halfCounts, currentLen - 1, kRem);52                    if (kRem <= perms) {53                        halfPerm.append((char) ('a' + j));54                        currentLen--;55                        break;56                    } else {57                        kRem -= perms;58                        halfCounts[j]++;59                    }60                }61            }62        }63 64        String reversedHalf = new StringBuilder(halfPerm).reverse().toString();65        return halfPerm.toString() + mid + reversedHalf;66    }67 68    private long countPerms(int[] counts, int len, long limit) {69        if (len == 0) return 1;70        long res = 1;71        int remLen = len;72        for (int count : counts) {73            if (count > 0) {74                long combinations = C[remLen][count];75                // Check for overflow before multiplication76                if (combinations > 0 && res > limit / combinations) {77                    return limit;78                }79                res *= combinations;80                if (res >= limit) return limit;81                remLen -= count;82            }83        }84        return res;85    }86}