LeetCode-in-Java

3518. Smallest Palindromic Rearrangement II

Hard

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

Solution

public class Solution {
    private static final long MAX_K = 1000001;

    public String smallestPalindrome(String inputStr, int k) {
        int[] frequency = new int[26];
        for (int i = 0; i < inputStr.length(); i++) {
            char ch = inputStr.charAt(i);
            frequency[ch - 'a']++;
        }
        char mid = 0;
        for (int i = 0; i < 26; i++) {
            if (frequency[i] % 2 == 1) {
                mid = (char) ('a' + i);
                frequency[i]--;
                break;
            }
        }
        int[] halfFreq = new int[26];
        int halfLength = 0;
        for (int i = 0; i < 26; i++) {
            halfFreq[i] = frequency[i] / 2;
            halfLength += halfFreq[i];
        }
        long totalPerms = multinomial(halfFreq);
        if (k > totalPerms) {
            return "";
        }
        StringBuilder firstHalfBuilder = new StringBuilder();
        for (int i = 0; i < halfLength; i++) {
            for (int c = 0; c < 26; c++) {
                if (halfFreq[c] > 0) {
                    halfFreq[c]--;
                    long perms = multinomial(halfFreq);
                    if (perms >= k) {
                        firstHalfBuilder.append((char) ('a' + c));
                        break;
                    } else {
                        k -= (int) perms;
                        halfFreq[c]++;
                    }
                }
            }
        }
        String firstHalf = firstHalfBuilder.toString();
        String revHalf = new StringBuilder(firstHalf).reverse().toString();
        String result;
        if (mid == 0) {
            result = firstHalf + revHalf;
        } else {
            result = firstHalf + mid + revHalf;
        }
        return result;
    }

    private long multinomial(int[] counts) {
        int tot = 0;
        for (int cnt : counts) {
            tot += cnt;
        }
        long res = 1;
        for (int i = 0; i < 26; i++) {
            int cnt = counts[i];
            res = res * binom(tot, cnt);
            if (res >= MAX_K) {
                return MAX_K;
            }
            tot -= cnt;
        }
        return res;
    }

    private long binom(int n, int k) {
        if (k > n) {
            return 0;
        }
        if (k > n - k) {
            k = n - k;
        }
        long result = 1;
        for (int i = 1; i <= k; i++) {
            result = result * (n - i + 1) / i;
            if (result >= MAX_K) {
                return MAX_K;
            }
        }
        return result;
    }
}

This site is open source. Improve this page.