Reorganizar los caracteres para formar palíndromo si es posible

Dada una string, convierta la string a palíndromo sin ninguna modificación, como agregar un carácter, eliminar un carácter, reemplazar un carácter, etc. 

Ejemplos: 

Input : "mdaam"
Output : "madam" or "amdma"

Input : "abb"
Output : "bab"

Input : "geeksforgeeks"
Output : "No Palindrome"

1. Cuente las ocurrencias de todos los caracteres. 
2. Cuente las ocurrencias impares. Si este recuento es mayor que 1 o es igual a 1 y la longitud de la string es par, entonces obviamente no se puede formar un palíndromo a partir de la string dada. 
3. Inicialice dos strings vacías firstHalf y secondHalf. 
4. Atraviesa el mapa. Para cada carácter con recuento como recuento, adjunte recuento/2 caracteres al final de la primera mitad y al comienzo de la segunda mitad. 
5. Finalmente devuelva el resultado agregando firstHalf y secondHalf

// C++ program to rearrange a string to
// make palindrome.
#include <bits/stdc++.h>
using namespace std;
 
string getPalindrome(string str)
{
 
    // Store counts of characters
    unordered_map<char, int> hmap;
    for (int i = 0; i < str.length(); i++)
        hmap[str[i]]++;
 
    /* find the number of odd elements.
       Takes O(n) */
    int oddCount = 0;
    char oddChar;
    for (auto x : hmap) {
        if (x.second % 2 != 0) {
            oddCount++;
            oddChar = x.first;
        }
    }
 
    /* odd_cnt = 1 only if the length of
       str is odd */
    if (oddCount > 1
        || oddCount == 1 && str.length() % 2 == 0)
        return "NO PALINDROME";
 
    /* Generate first half of palindrome */
    string firstHalf = "", secondHalf = "";
    for (auto x : hmap) {
 
        // Build a string of floor(count/2)
        // occurrences of current character
        string s(x.second / 2, x.first);
 
        // Attach the built string to end of
        // and begin of second half
        firstHalf = firstHalf + s;
        secondHalf = s + secondHalf;
    }
 
    // Insert odd character if there
    // is any
    return (oddCount == 1)
               ? (firstHalf + oddChar + secondHalf)
               : (firstHalf + secondHalf);
}
 
int main()
{
    string s = "mdaam";
    cout << getPalindrome(s);
    return 0;
}

// Java program to rearrange a string to
// make palindrome
import java.util.HashMap;
import java.util.Map.Entry;
 
class GFG{
 
public static String getPalindrome(String str)
{
     
    // Store counts of characters
    HashMap<Character,
            Integer> counting = new HashMap<>();
    for(char ch : str.toCharArray())
    {
        if (counting.containsKey(ch))
        {
            counting.put(ch, counting.get(ch) + 1);
        }
        else
        {
            counting.put(ch, 1);
        }
    }
     
    /* Find the number of odd elements.
    Takes O(n) */
    int oddCount = 0;
    char oddChar = 0;
     
    for(Entry<Character,
              Integer> itr : counting.entrySet())
    {
        if (itr.getValue() % 2 != 0)
        {
            oddCount++;
            oddChar = itr.getKey();
        }
    }
     
    /* odd_cnt = 1 only if the length of
    str is odd */
    if (oddCount > 1 || oddCount == 1 &&
        str.length() % 2 == 0)
    {
        return "NO PALINDROME";
    }
     
    /* Generate first half of palindrome */
    String firstHalf = "", lastHalf = "";
    for(Entry<Character, Integer> itr : counting.entrySet())
    {
         
        // Build a string of floor(count/2)
        // occurrences of current character
        String ss = "";
        for(int i = 0; i < itr.getValue() / 2; i++)
        {
            ss += itr.getKey();
        }
         
        // Attach the built string to end of
        // and begin of second half
        firstHalf = firstHalf + ss;
        lastHalf = ss + lastHalf;
    }
     
    // Insert odd character if there
    // is any
    return (oddCount == 1) ?
           (firstHalf + oddChar + lastHalf) :
           (firstHalf + lastHalf);
}
 
// Driver code
public static void main(String[] args)
{
    String str = "mdaam";
    System.out.println(getPalindrome(str));
}
}
 
// This code is contributed by Satyam Singh

# Python3 program to rearrange a string to
# make palindrome.
from collections import defaultdict
 
 
def getPalindrome(st):
 
    # Store counts of characters
    hmap = defaultdict(int)
    for i in range(len(st)):
        hmap[st[i]] += 1
 
    # Find the number of odd elements.
    # Takes O(n)
    oddCount = 0
 
    for x in hmap:
        if (hmap[x] % 2 != 0):
            oddCount += 1
            oddChar = x
 
    # odd_cnt = 1 only if the length of
    # str is odd
    if (oddCount > 1 or oddCount == 1 and
            len(st) % 2 == 0):
        return "NO PALINDROME"
 
    # Generate first half of palindrome
    firstHalf = ""
    secondHalf = ""
 
    for x in sorted(hmap.keys()):
 
        # Build a string of floor(count/2)
        # occurrences of current character
        s = (hmap[x] // 2) * x
 
        # Attach the built string to end of
        # and begin of second half
        firstHalf = firstHalf + s
        secondHalf = s + secondHalf
 
    # Insert odd character if there
    # is any
    if (oddCount == 1):
        return (firstHalf + oddChar + secondHalf)
    else:
        return (firstHalf + secondHalf)
 
 
# Driver code
if __name__ == "__main__":
 
    s = "mdaam"
 
    print(getPalindrome(s))
 
# This code is contributed by ukasp

<script>
 
// JavaScript program to rearrange a string to
// make palindrome.
function getPalindrome(str)
{
 
    // Store counts of characters
    let hmap = new Map();
    for (let i = 0; i < str.length; i++){
        if(hmap.has(str[i])){
            hmap.set(str[i],hmap.get(str[i])+1);
        }
        else{
            hmap.set(str[i],1);
        }
    }
 
    /* find the number of odd elements.
       Takes O(n) */
    let oddCount = 0;
    let oddChar;
    for (let [x,y] of hmap) {
        if (y % 2 != 0) {
            oddCount++;
            oddChar = x;
        }
    }
 
    /* odd_cnt = 1 only if the length of
       str is odd */
    if (oddCount > 1
        || oddCount == 1 && str.length % 2 == 0)
        return "NO PALINDROME";
 
    /* Generate first half of palindrome */
    let firstHalf = "", secondHalf = "";
    for (let [x,y] of hmap) {
 
        // Build a string of floor(count/2)
        // occurrences of current character
        let s = "";
        for(let i = 0; i < Math.floor(y/2); i++){
             s += x;
        }
 
        // Attach the built string to end of
        // and begin of second half
        firstHalf = firstHalf + s;
        secondHalf = s + secondHalf;
    }
 
    // Insert odd character if there
    // is any
    return (oddCount == 1)
               ? (firstHalf + oddChar + secondHalf)
               : (firstHalf + secondHalf);
}
 
// driver program
let s = "mdaam";
document.write(getPalindrome(s));
 
// This code is contributed by shinjanpatra.
</script>

amdma