Smallest Palindromic Rearrangement II

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.

Examples

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 <= 10^4
• s consists of lowercase English letters.
• s is guaranteed to be palindromic.
• 1 <= k <= 10^6

Solution

Method 1 - Combinatorics (construct k-th multiset permutation of the first half)

Intuition

A palindrome is fully determined by its first half (and an optional middle character when length is odd). Distinct palindromes correspond to distinct permutations of the multiset formed by taking half the counts of each character from s. We can greedily build the k-th lexicographic palindrome by deciding each position of the first half: for each candidate character, count how many permutations would start with that prefix; skip whole blocks until we locate the block containing the k-th permutation.

Approach

• Count frequencies for all 26 lowercase letters.
• Determine mid (the single odd-count character) and halfCnt[i] = freq[i] / 2.
• Let halfLen = sum(halfCnt). The number of distinct palindromes equals permutations of this multiset.
• Use a capped combination function comb(n, r, cap) returning min(C(n, r), cap) to avoid big integers.
• To build the first half (positions 0..halfLen-1):
  1. For each character c from 'a' to 'z' with halfCnt[c] > 0, tentatively decrement halfCnt[c].
  2. Compute how many permutations can be formed with remaining counts; if that count < k, subtract and continue.
  3. Otherwise pick c and proceed to next position.
• After first half is built, assemble result first + mid + reverse(first).

Edge cases:

• If total number of palindromes < k, return empty string.
• Cap all intermediate counts with cap = k + 1 so any count >= k is treated as "enough".

Code

C++

class Solution {
public:
    string smallestPalindrome(string s, int k) {
        long long cap = (long long)k + 1;
        vector<int> freq(26, 0);
        for (char ch : s) freq[ch - 'a']++;
        string mid = "";
        for (int i = 0; i < 26; ++i) if (freq[i] % 2) mid.push_back('a' + i);
        vector<int> half(26, 0);
        int halfLen = 0;
        for (int i = 0; i < 26; ++i) { half[i] = freq[i] / 2; halfLen += half[i]; }

        auto comb = [&](int n, int r)->long long{
            if (r < 0 || r > n) return 0;
            r = min(r, n - r);
            long long res = 1;
            for (int i = 1; i <= r; ++i) {
                res = res * (n - r + i) / i;
                if (res >= cap) return cap;
            }
            return res;
        };

        function<long long(const vector<int>&, int)> countPerms = [&](const vector<int>& counts, int rem)->long long{
            long long ways = 1;
            int r = rem;
            for (int c : counts) {
                if (c == 0) continue;
                long long w = comb(r, c);
                ways = ways * w;
                if (ways >= cap) return cap;
                r -= c;
            }
            return ways;
        };

        long long total = countPerms(half, halfLen);
        if (total < k) return "";
        string first = "";
        for (int pos = 0; pos < halfLen; ++pos) {
            for (int ch = 0; ch < 26; ++ch) {
                if (half[ch] == 0) continue;
                half[ch]--;
                long long cnt = countPerms(half, halfLen - pos - 1);
                if (cnt < k) {
                    k -= (int)cnt;
                    half[ch]++;
                } else {
                    first.push_back('a' + ch);
                    break;
                }
            }
        }
        string rev = first;
        reverse(rev.begin(), rev.end());
        return first + mid + rev;
    }
};

Go

package main

func smallestPalindrome(s string, k int) string {
    cap := int64(k) + 1
    freq := make([]int, 26)
    for _, ch := range s { freq[int(ch-'a')]++ }
    mid := ""
    for i := 0; i < 26; i++ { if freq[i]%2 == 1 { mid = string(byte('a'+i)) } }
    half := make([]int, 26)
    halfLen := 0
    for i := 0; i < 26; i++ { half[i] = freq[i] / 2; halfLen += half[i] }
    comb := func(n, r int) int64 {
        if r < 0 || r > n { return 0 }
        if r > n-r { r = n-r }
        var res int64 = 1
        for i := 1; i <= r; i++ {
            res = res * int64(n-r+i) / int64(i)
            if res >= cap { return cap }
        }
        return res
    }
    countPerms := func(counts []int, rem int) int64 {
        var ways int64 = 1
        r := rem
        for _, c := range counts {
            if c == 0 { continue }
            w := comb(r, c)
            ways = ways * w
            if ways >= cap { return cap }
            r -= c
        }
        return ways
    }
    total := countPerms(half, halfLen)
    if total < int64(k) { return "" }
    first := make([]byte, 0, halfLen)
    for pos := 0; pos < halfLen; pos++ {
        for ch := 0; ch < 26; ch++ {
            if half[ch] == 0 { continue }
            half[ch]--
            cnt := countPerms(half, halfLen-pos-1)
            if cnt < int64(k) {
                k -= int(cnt)
                half[ch]++
            } else {
                first = append(first, byte('a'+ch))
                break
            }
        }
    }
    rev := make([]byte, len(first))
    for i := range first { rev[len(first)-1-i] = first[i] }
    return string(first) + mid + string(rev)
}

Java

class Solution {
    public String smallestPalindrome(String s, int k) {
        long cap = (long)k + 1;
        int[] freq = new int[26];
        for (char ch : s.toCharArray()) freq[ch - 'a']++;
        String mid = "";
        for (int i = 0; i < 26; i++) if (freq[i] % 2 == 1) mid = String.valueOf((char)('a' + i));
        int[] half = new int[26];
        int halfLen = 0;
        for (int i = 0; i < 26; i++) { half[i] = freq[i] / 2; halfLen += half[i]; }
        java.util.function.BiFunction<Integer,Integer,Long> comb = (n,r) -> {
            if (r < 0 || r > n) return 0L;
            r = Math.min(r, n - r);
            long res = 1;
            for (int i = 1; i <= r; i++) {
                res = res * (n - r + i) / i;
                if (res >= cap) return cap;
            }
            return res;
        };
        java.util.function.BiFunction<int[],Integer,Long> countPerms = (counts, rem) -> {
            long ways = 1;
            int r = rem;
            for (int c : counts) {
                if (c == 0) continue;
                long w = comb.apply(r, c);
                ways = ways * w;
                if (ways >= cap) return cap;
                r -= c;
            }
            return ways;
        };
        long total = countPerms.apply(half, halfLen);
        if (total < k) return "";
        StringBuilder first = new StringBuilder();
        for (int pos = 0; pos < halfLen; pos++) {
            for (int ch = 0; ch < 26; ch++) {
                if (half[ch] == 0) continue;
                half[ch]--;
                long cnt = countPerms.apply(half, halfLen - pos - 1);
                if (cnt < k) {
                    k -= (int)cnt;
                    half[ch]++;
                } else {
                    first.append((char)('a' + ch));
                    break;
                }
            }
        }
        String rev = new StringBuilder(first).reverse().toString();
        return first.toString() + mid + rev;
    }
}

Kotlin

class Solution {
    fun smallestPalindrome(s: String, k: Int): String {
        val cap = k.toLong() + 1
        val freq = IntArray(26)
        for (ch in s) freq[ch - 'a']++
        var mid = ""
        for (i in 0 until 26) if (freq[i] % 2 == 1) mid = ('a' + i).toString()
        val half = IntArray(26)
        var halfLen = 0
        for (i in 0 until 26) { half[i] = freq[i] / 2; halfLen += half[i] }
        fun comb(n: Int, r: Int): Long {
            if (r < 0 || r > n) return 0
            var rr = r
            if (rr > n - rr) rr = n - rr
            var res = 1L
            for (i in 1..rr) {
                res = res * (n - rr + i) / i
                if (res >= cap) return cap
            }
            return res
        }
        fun countPerms(counts: IntArray, rem: Int): Long {
            var ways = 1L
            var r = rem
            for (c in counts) {
                if (c == 0) continue
                val w = comb(r, c)
                ways = ways * w
                if (ways >= cap) return cap
                r -= c
            }
            return ways
        }
        val total = countPerms(half, halfLen)
        if (total < k) return ""
        val first = StringBuilder()
        var kk = k
        for (pos in 0 until halfLen) {
            for (ch in 0 until 26) {
                if (half[ch] == 0) continue
                half[ch]--
                val cnt = countPerms(half, halfLen - pos - 1)
                if (cnt < kk) {
                    kk -= cnt.toInt()
                    half[ch]++
                } else {
                    first.append('a' + ch)
                    break
                }
            }
        }
        val rev = first.toString().reversed()
        return first.toString() + mid + rev
    }
}

Python

class Solution:
    def smallestPalindrome(self, s: str, k: int) -> str:
        cap = k + 1
        freq = [0] * 26
        for ch in s: freq[ord(ch) - 97] += 1
        mid = ""
        for i in range(26):
            if freq[i] % 2:
                mid = chr(97 + i)
        half = [f // 2 for f in freq]
        half_len = sum(half)
        def comb(n: int, r: int) -> int:
            if r < 0 or r > n: return 0
            r = min(r, n - r)
            res = 1
            for i in range(1, r + 1):
                res = res * (n - r + i) // i
                if res >= cap: return cap
            return res
        def count_perms(counts: list[int], rem: int) -> int:
            ways = 1
            r = rem
            for c in counts:
                if c == 0: continue
                w = comb(r, c)
                ways = ways * w
                if ways >= cap: return cap
                r -= c
            return ways
        total = count_perms(half, half_len)
        if total < k: return ""
        first = []
        for pos in range(half_len):
            for ch in range(26):
                if half[ch] == 0: continue
                half[ch] -= 1
                cnt = count_perms(half, half_len - pos - 1)
                if cnt < k:
                    k -= cnt
                    half[ch] += 1
                else:
                    first.append(chr(97 + ch))
                    break
        ans = ''.join(first)
        return ans + mid + ans[::-1]

Rust

pub struct Solution;
impl Solution {
    pub fn smallest_palindrome(s: String, k: i32) -> String {
        let cap = (k as i64) + 1;
        let mut freq = vec![0i32; 26];
        for b in s.bytes() { freq[(b - b'a') as usize] += 1; }
        let mut mid = String::new();
        for i in 0..26 { if freq[i] % 2 != 0 { mid.push((b'a' + i as u8) as char); } }
        let mut half = vec![0i32; 26];
        let mut half_len = 0;
        for i in 0..26 { half[i] = freq[i] / 2; half_len += half[i]; }
        fn comb(n: i32, r: i32, cap: i64) -> i64 {
            if r < 0 || r > n { return 0; }
            let mut rr = r;
            if rr > n - rr { rr = n - rr; }
            let mut res: i64 = 1;
            for i in 1..=rr {
                res = res * ((n - rr + i) as i64) / (i as i64);
                if res >= cap { return cap; }
            }
            res
        }
        fn count_perms(counts: &Vec<i32>, rem: i32, cap: i64) -> i64 {
            let mut ways: i64 = 1;
            let mut r = rem;
            for &c in counts.iter() {
                if c == 0 { continue; }
                let w = comb(r, c, cap);
                ways = ways * w;
                if ways >= cap { return cap; }
                r -= c;
            }
            ways
        }
        let total = count_perms(&half, half_len, cap);
        if total < k as i64 { return String::new(); }
        let mut first = String::new();
        let mut kk = k;
        for pos in 0..half_len {
            for ch in 0..26 {
                if half[ch] == 0 { continue; }
                half[ch] -= 1;
                let cnt = count_perms(&half, half_len - pos - 1, cap);
                if cnt < kk as i64 {
                    kk -= cnt as i32;
                    half[ch] += 1;
                } else {
                    first.push((b'a' + ch as u8) as char);
                    break;
                }
            }
        }
        let rev: String = first.chars().rev().collect();
        format!("{}{}{}", first, mid, rev)
    }
}

TypeScript

export class Solution {
    smallestPalindrome(s: string, k: number): string {
        const cap = k + 1;
        const freq = new Array(26).fill(0);
        for (const ch of s) freq[ch.charCodeAt(0) - 97]++;
        let mid = "";
        for (let i = 0; i < 26; i++) if (freq[i] % 2 === 1) mid = String.fromCharCode(97 + i);
        const half = new Array(26).fill(0);
        let halfLen = 0;
        for (let i = 0; i < 26; i++) { half[i] = Math.floor(freq[i] / 2); halfLen += half[i]; }
        const comb = (n: number, r: number): number => {
            if (r < 0 || r > n) return 0;
            if (r > n - r) r = n - r;
            let res = 1;
            for (let i = 1; i <= r; i++) {
                res = Math.floor(res * (n - r + i) / i);
                if (res >= cap) return cap;
            }
            return res;
        };
        const countPerms = (counts: number[], rem: number): number => {
            let ways = 1;
            let r = rem;
            for (const c of counts) {
                if (c === 0) continue;
                const w = comb(r, c);
                ways = ways * w;
                if (ways >= cap) return cap;
                r -= c;
            }
            return ways;
        };
        const total = countPerms(half, halfLen);
        if (total < k) return "";
        const first: string[] = [];
        for (let pos = 0; pos < halfLen; pos++) {
            for (let ch = 0; ch < 26; ch++) {
                if (half[ch] === 0) continue;
                half[ch]--;
                const cnt = countPerms(half, halfLen - pos - 1);
                if (cnt < k) { k -= cnt; half[ch]++; }
                else { first.push(String.fromCharCode(97 + ch)); break; }
            }
        }
        const ans = first.join("");
        return ans + mid + ans.split("").reverse().join("");
    }
}