Eliminación mínima para hacer permutación de palíndromo

Dada una string S, tenemos que encontrar un mínimo de caracteres que podamos eliminar para hacer que cualquier permutación de la string S sea un palíndromo. 
En términos simples, el problema establece que: Convierta la string en un palíndromo reorganizándola de cualquier manera eliminando la cantidad mínima de caracteres, incluida la eliminación de 0 caracteres si es posible.
Nota : estamos considerando solo alfabetos pequeños. 
Ejemplos: 
 

Input :  geeksforgeeks
Output : 2
Explanation : if we remove 2 characters lets 
say 'f' and 'r',  we remain with "geeksogeeks" 
which can be re-arranged like "skeegogeeks" 
to make it a palindrome. Removal of less than 
2 character wouldn't make this string a 
palindrome.

Input :  shubham
Output : 4
If we remove any 4 characters except 'h' (let's
say 's', 'b', 'a', 'm'),  we remain with "huh" 
which is a palindrome.

Un enfoque ingenuo verificaría cada permutación de la string en busca de palíndromo y, si no se encuentra, eliminaría un carácter y volvería a verificar. Este enfoque es muy complicado y llevará mucho tiempo.
Un enfoque eficiente sería notar que no necesitamos imprimir los caracteres mínimos, solo el número mínimo. Entonces, una idea efectiva es la clave de que: puede haber dos tipos de palíndromo, palíndromo de longitud par y palíndromo de longitud impar. Podemos deducir el hecho de que un palíndromo de longitud par debe tener todos los caracteres que ocurren un número par de veces (es decir, la frecuencia de cada carácter es par). De manera similar, un palíndromo impar debe tener todos los caracteres que aparecen un número par de veces, excepto un carácter que aparece un número impar de veces.
A partir de estos hechos, el problema resulta ser bastante simple. Verificamos la frecuencia de cada carácter y luego se cuentan aquellos caracteres que ocurren un número impar de veces. Luego, el resultado es el recuento total de caracteres de frecuencia impar restando 1. 
 

// CPP Program to find minimum number of removal to
// make any permutation of the string a palindrome
#include <iostream>
using namespace std;
 
#define MAX_CHAR 26
 
// function to find minimum removal of characters
int minRemoval(string str) {
 
  // hash to store frequency of each character
  int hash[MAX_CHAR];
 
  // to set hash array to zeros
  memset(hash, 0, sizeof(hash));
 
  // count frequency of each character
  for (int i = 0; str[i]; i++)
    hash[str[i] - 'a']++;
 
  // count the odd frequency characters
  int count = 0;
  for (int i = 0; i < MAX_CHAR; i++)
    if (hash[i] % 2)
      count++;
 
  // if count is -1 return 0
  // otherwise return count
  return (count == 0) ? 0 : count-1;
}
 
// Driver's Code
int main() {
  string str = "geeksforgeeks";
  cout << minRemoval(str) << endl;
  return 0;
}

// Java Program to find minimum number of removal to
// make any permutation of the string a palindrome
import java.util.Arrays;
class GFG {
  static final int MAX_CHAR = 26;
 
  // function to find minimum removal of characters
  static int minRemoval(String str) {
 
    // hash to store frequency of each character
    int hash[] = new int[MAX_CHAR];
 
    // to set hash array to zeros
    Arrays.fill(hash, 0);
 
    // count frequency of each character
    for (int i = 0; i < str.length(); i++)
      hash[str.charAt(i) - 'a']++;
 
    // count the odd frequency characters
    int count = 0;
    for (int i = 0; i < MAX_CHAR; i++)
      if (hash[i] % 2 == 1)
        count++;
 
    // if count is -1 return 0
    // otherwise return count
    return (count == 0) ? 0 : count - 1;
  }
  // Driver code
  public static void main(String[] args) {
    String str = "geeksforgeeks";
    System.out.println(minRemoval(str));
  }
}
// This code is contributed by Anant Agarwal.

# Python Program to find minimum number of
# removal to make any permutation of the
# string a palindrome
 
# function to find minimum removal of
# characters
def minRemoval(strr):
     
        # hash to store frequency of each character
        # to set hash array to zeros
        hash = [0] * 26
 
        # count frequency of each character
        for char in strr:
                hash[ord(char)-ord('a')] = hash[ord(char)-ord('a')] + 1
 
        # count the odd frequency characters
        count = 0
        for i in range(26):
                if hash[i]% 2:
                        count = count + 1
 
        # if count is 0, return 0
        # otherwise return count
        return 0 if count == 0 else count-1
 
 
# Driver's Code
if __name__ == "__main__":
     
        strr = "geeksforgeeks";
 
        # minRemoval to find minimum characters to remove
        print(minRemoval(strr))

// C# Program to find minimum number of
// removal to make any permutation of
// the string a palindrome
using System;
 
class GFG {
     
    static int MAX_CHAR = 26;
     
    // function to find minimum removal
    // of characters
    static int minRemoval(string str) {
     
        // hash to store frequency of
        // each character
        int []hash = new int[MAX_CHAR];
     
        // to set hash array to zeros
        for(int i = 0; i < MAX_CHAR; i++)
        hash[i] = 0;
     
        // count frequency of each character
        for (int i = 0; i < str.Length; i++)
        hash[str[i] - 'a']++;
     
        // count the odd frequency characters
        int count = 0;
        for (int i = 0; i < MAX_CHAR; i++)
        if (hash[i] % 2 == 1)
            count++;
     
        // if count is -1 return 0
        // otherwise return count
        return (count == 0) ? 0 : count - 1;
    }
     
    // Driver code
    public static void Main() {
        string str = "geeksforgeeks";
        Console.Write(minRemoval(str));
    }
}
 
// This code is contributed by nitin mittal

<?php
// PHP Program to find minimum
// number of removal to make any
// permutation of the string a palindrome
 
// function to find minimum
// removal of characters
function minRemoval($str)
{
     
    // hash to store frequency of each
    // character and to set hash array to zeros
    $hash = array_fill(0, 26, 0);
     
    // count frequency of each character
    for ($i = 0; $i < strlen($str); $i++)
        $hash[ord($str[$i]) - 97]++;
     
    // count the odd frequency characters
    $count = 0;
    for ($i = 0; $i < 26; $i++)
        if ($hash[$i] % 2)
        $count++;
     
    // if count is -1 return 0
    // otherwise return count
    return ($count == 0) ? 0 : $count-1;
}
 
// Driver Code
$str = "geeksforgeeks";
echo minRemoval($str)."\n";
 
// This code is contributed by mits
?>

<script>
// Javascript Program to find minimum number of removal to
// make any permutation of the string a palindrome
 
var MAX_CHAR = 26
 
// function to find minimum removal of characters
function minRemoval( str)
{
 
  // hash to store frequency of each character
  var hash = Array(MAX_CHAR).fill(0);
 
  // count frequency of each character
  for (var i = 0; str[i]; i++)
    hash[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
 
  // count the odd frequency characters
  var count = 0;
  for (var i = 0; i < MAX_CHAR; i++)
    if (hash[i] % 2)
      count++;
 
  // if count is -1 return 0
  // otherwise return count
  return (count == 0) ? 0 : count-1;
}
 
// Driver's Code
var str = "geeksforgeeks";
document.write( minRemoval(str));
 
// This code is contributed by itsok.
</script>

Producción : 
 

2