K-th DuoPalindrome

Each half of the DuoPalindrome will be the same. And since these halves are palindromes as well, we only need to find the half these half (or the quarter) to get our desired DuoPalindrome. Therefore we can deduce that, each letter in the string will appear 4 times, except for possibly one letter, which will appear 2 times (depending on whether the length of the 'half' is even or odd). Make a new string consisting of the letters that appear 4 times (each letter will appear only once in the new string). Find the K-th lexicographical smallest ordering of that string which indicates our 'quarter'. Then concatenate the 'quarter' with its reverse to get the 'half'. If there's a letter that appears 2 times, don't forget to add it in middle of the 'half'. Then of course, concatenate the 'half' with itself to get the final result.

Since each of the letters will appear only once in the 'quarter', it's fairly easy to find the K-th lexicographical ordering of it. See the C++ implementation below for details.

#include <bits/stdc++.h>
using namespace std;

int n,taken[102]; 
string s,rs; 

int main () {
    long long k,fact[102];
    long long MAXA = 1e16; 
    int id = -1;
    
    memset(fact,-1,sizeof(fact));

    fact[0] = 1; 

    for(int i = 1; i <= 26; i++){
        if(fact[i-1] > MAXA) break; 
        fact[i] = fact[i-1] * i; 
    }

    cin >> s >> k;

    for(int i = 0; i < s.size(); i++) {
        taken[s[i]-'a']++;
    }

    for(int i = 0; i < 26; i++) {

        if(taken[i] == 4) n++;
        else if(taken[i] == 2) id = i;
    }

    for(int i = 0; i < n; i++) {
        //fixing i-th position here

        for(int j = 0; j < 26; j++) {
            
            if(taken[j] == 4) {

                int rem = n-i-1;

                if(fact[rem] == -1 || fact[rem] >= k) { 
                    
                    taken[j] = 0; 
                    rs += 'a'+j; 
                    break; 
                }

                else {
                    k -= fact[rem];
                }
            }
        }
    }

    string tmp = rs; 
    reverse(tmp.begin(), tmp.end());

    if(id != -1) { 
        char ch = id+'a';
        rs += ch;        
    }

    rs += tmp;
    rs += rs;
    
    cout << rs << endl;
 
    return 0;
}