Cree un palíndromo lexicográficamente más pequeño con cambios mínimos

Dada una string S. Imprima la string lexicográficamente más pequeña posible. Puede realizar cambios mínimos en los caracteres de la string y puede permutar la string.

Ejemplos:

Input : S = "aabc"
Output : "abba"

Input : S = "äabcd"
Output : "abcba"

Explicación 1: Cambie el último índice «c» a «b», se convierte en «aabb». Luego reorganice la string, se convierte en «abba». Esta es la string lexicográficamente más pequeña.
Explicación 2: cambia “d” por “b” => “aabcb” => “abcba”.

Enfoque:
cnt[a] sea el número de ocurrencias del carácter a. Considere valores impares de cnt[a], entonces un palíndromo no puede contener más de un carácter a con cnt[a]. Indique caracteres con conteo impar cnt[] como sigue a ₁ , a ₂ ….a _k (en orden alfabético). Reemplace cualquiera de los símbolos _ak con un ₁ y _ak-1 con un ₂ y así sucesivamente hasta la mitad de la secuencia anterior. Ahora, no hay más de un símbolo impar. Colóquelo en el medio de la respuesta. La primera mitad de la respuesta consistirá en ocurrencias del símbolo a. La segunda mitad contendrá los mismos símbolos en orden inverso.
Ejemplo :

  take string S =  "aabcd"
  cnt[a] = 2, cnt[b] = 1, cnt = 1, cnt[d] = 1.
 Odd characters => b, c, d
  replace ak('d') with a1('b') we get => b, c, b.
  cnt[b] = 2, cnt = 1.Place odd character in middle 
   and 'a' and 'b' in first half and also in second half,
   we get "abcba".

// CPP code for changing a string
// into lexicographically smallest
// pallindromic string
#include <bits/stdc++.h>
using namespace std;
  
// Function to create a palindrome
int Palindrome(string s, int n)
{
    unordered_map<char, int> cnt;
    string R = "";
  
    // Count the occurrences of
    // every character in the string
    for (int i = 0; i < n; i++) {
        char a = s[i];
        cnt[a]++;
    }
  
    // Create a string of characters
    // with odd occurrences
    for (char i = 'a'; i <= 'z'; i++) {
        if (cnt[i] % 2 != 0)
            R += i;
    }
  
    int l = R.length();
    int j = 0;
  
    // Change the created string upto
    // middle element and update
    // count to make sure that only
    // one odd character exists.
    for (int i = l - 1; i >= l / 2; i--) {
  
        // decrease the count of
        // character updated
        cnt[R[i]]--;
        R[i] = R[j];
        cnt[R[j]]++;
        j++;
    }
  
    // Create three strings to make
    // first half second half and
    // middle one.
    string first, middle, second;
  
    for (char i = 'a'; i <= 'z'; i++) {
        if (cnt[i] != 0) {
  
            // characters with even occurrences
            if (cnt[i] % 2 == 0) {
                int j = 0;
  
                // fill the first half.
                while (j < cnt[i] / 2) {
                    first += i;
                    j++;
                }
            }
  
            // character with odd occurrence
            else {
                int j = 0;
  
                // fill the first half with
                // half of occurrence except one
                while (j < (cnt[i] - 1) / 2) {
                    first += i;
                    j++;
                }
  
                // For middle element
                middle += i;
            }
        }
    }
  
    // create the second half by
    // reversing the first half.
    second = first;
    reverse(second.begin(), second.end());
    string resultant = first + middle + second;
    cout << resultant << endl;
}
  
// Driver code
int main()
{
    string S = "geeksforgeeks";
    int n = S.length();
    Palindrome(S, n);
    return 0;
}

# Python code for changing a string
# into lexicographically smallest
# pallindromic string
  
# Function to create a palindrome
def palindrome(s: str, n: int) -> int:
    cnt = dict()
    R = []
  
    # Count the occurrences of
    # every character in the string
    for i in range(n):
        a = s[i]
        if a in cnt:
            cnt[a] += 1
        else:
            cnt[a] = 1
  
    # Create a string of characters
    # with odd occurrences
    i = 'a'
    while i <= 'z':
        if i in cnt and cnt[i] % 2 != 0:
            R += i
        i = chr(ord(i) + 1)
  
    l = len(R)
    j = 0
  
    # Change the created string upto
    # middle element and update
    # count to make sure that only
    # one odd character exists.
    for i in range(l - 1, (l // 2) - 1, -1):
  
        # decrease the count of
        # character updated
        if R[i] in cnt:
            cnt[R[i]] -= 1
        else:
            cnt[R[i]] = -1
  
        R[i] = R[j]
  
        if R[j] in cnt:
            cnt[R[j]] += 1
        else:
            cnt[R[j]] = 1
        j += 1
  
    # Create three strings to make
    # first half second half and
    # middle one.
    first, middle, second = "", "", ""
  
    i = 'a'
    while i <= 'z':
        if i in cnt:
  
            # characters with even occurrences
            if cnt[i] % 2 == 0:
                j = 0
  
                # fill the first half.
                while j < cnt[i] // 2:
                    first += i
                    j += 1
  
            # character with odd occurrence
            else:
                j = 0
  
                # fill the first half with
                # half of occurrence except one
                while j < (cnt[i] - 1) // 2:
                    first += i
                    j += 1
  
                # For middle element
                middle += i
        i = chr(ord(i) + 1)
  
    # create the second half by
    # reversing the first half.
    second = first
    second = ''.join(reversed(second))
    resultant = first + middle + second
    print(resultant)
  
# Driver Code
if __name__ == "__main__":
  
    S = "geeksforgeeks"
    n = len(S)
    palindrome(S, n)
  
# This code is contributed by
# sanjeev2552

 eefgksoskgfee