Eliminaciones mínimas requeridas para que una string se pueda reorganizar para formar un palíndromo

Dada una string S que consta de alfabetos ingleses en minúsculas, la tarea es encontrar el número mínimo de caracteres necesarios para eliminar de modo que los caracteres de la string puedan reorganizarse para formar un palíndromo .

Ejemplos: 

Entrada: S = “ababccca”
Salida: 1
Explicación:
elimine la aparición de ‘c’ de la string. Por lo tanto, la string modificada es «ababcca», que se puede reorganizar para formar la string palindrómica «cababac».
Por lo tanto, solo se requiere una eliminación.

Entrada: S = abcde
Salida: 4 

Planteamiento: El problema se puede resolver basándose en la observación de que, en una string palindrómica , como máximo un carácter puede aparecer un número impar de veces. Por lo tanto, reduzca la frecuencia de todos los caracteres impares excepto uno de ellos. 
Siga los pasos a continuación para resolver el problema: 

• Inicialice una array de tamaño 26 para almacenar la frecuencia de cada carácter en S .
• Atraviesa la cuerda
• Actualice la frecuencia de cada carácter en la array de frecuencia.
• Cuente el número de caracteres que tienen una frecuencia impar y guárdelo en una variable, digamos count .
• Si el conteo es 1 o 0 , imprima 0 como respuesta. De lo contrario, imprima el conteo – 1 como respuesta.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of deletions
// required such that characters of the
// string can be rearranged to form a palindrome
int minDeletions(string str)
{
    // Stores frequency of characters
    int fre[26];
    memset(fre, 0, sizeof(fre));
 
    int n = str.size();
cout<<n;
    // Store the frequency of each
    // character in frequency array
    for (int i = 0; i < n; i++) {
        fre[str[i] - 'a'] += 1;
    }
      for (int i = 0; i < n; i++) {
        cout<<fre[i];
    }
  
 
    int count = 0;
 
    // Count number of characters
    // with odd frequency
    for (int i = 0; i < 26; i++) {
        if (fre[i] % 2) {
            count += 1;
        }
    }
 
    // If count is 1 or 0, return 0
    if (count == 0 || count == 1) {
        return 0;
    }
 
    // Otherwise, return count - 1
    else {
        return count - 1;
    }
}
 
// Driver Code
int main()
{
    string str = "ababbccca";
 
    // Function call to find minimum
    // number of deletions required
    cout << minDeletions(str) << endl;
}

// Java program for the above approach
public class GFG
{
 
  // Function to find the number of deletions
  // required such that characters of the
  // string can be rearranged to form a palindrome
  static int minDeletions(String str)
  {
    // Stores frequency of characters
    int fre[] = new int[26];
 
    int n = str.length();
 
    // Store the frequency of each
    // character in frequency array
    for (int i = 0; i < n; i++) {
      fre[str.charAt(i) - 'a'] += 1;
    }
 
    int count = 0;
 
    // Count number of characters
    // with odd frequency
    for (int i = 0; i < 26; i++) {
      if (fre[i] % 2 == 1) {
        count += 1;
      }
    }
 
    // If count is 1 or 0, return 0
    if (count == 0 || count == 1) {
      return 0;
    }
 
    // Otherwise, return count - 1
    else {
      return count - 1;
    }
  }
 
  // Driver Code
  public static void main (String[] args)
  {
    String str = "ababbccca";
 
    // Function call to find minimum
    // number of deletions required
    System.out.println(minDeletions(str)) ;
  }
}
 
// This code is contributed by AnkThon

# Python3 program for
# the above approach
 
# Function to find the number of deletions
# required such that characters of the
# string can be rearranged to form a palindrome
def minDeletions(str):
     
    # Stores frequency of characters
    fre = [0]*26
     
    # memset(fre, 0, sizeof(fre));
    n = len(str)
 
    # Store the frequency of each
    # character in frequency array
    for i in range(n):
        fre[ord(str[i]) - ord('a')] += 1
 
    count = 0
 
    # Count number of characters
    # with odd frequency
    for i in range(26):
        if (fre[i] % 2):
            count += 1
 
    # If count is 1 or 0, return 0
    if (count == 0 or count == 1):
        return 0
 
    # Otherwise, return count - 1
    else:
        return count - 1
 
# Driver Code
if __name__ == '__main__':
    str = "ababbccca"
 
    # Function call to find minimum
    # number of deletions required
    print (minDeletions(str))
 
    # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
public class GFG
{
 
  // Function to find the number of deletions
  // required such that characters of the
  // string can be rearranged to form a palindrome
  static int minDeletions(string str)
  {
 
    // Stores frequency of characters
    int []fre = new int[26];
    int n = str.Length;
 
    // Store the frequency of each
    // character in frequency array
    for (int i = 0; i < n; i++)
    {
      fre[str[i] - 'a'] += 1;
    }
 
    int count = 0;
 
    // Count number of characters
    // with odd frequency
    for (int i = 0; i < 26; i++) {
      if (fre[i] % 2 == 1) {
        count += 1;
      }
    }
 
    // If count is 1 or 0, return 0
    if (count == 0 || count == 1) {
      return 0;
    }
 
    // Otherwise, return count - 1
    else {
      return count - 1;
    }
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    string str = "ababbccca";
 
    // Function call to find minimum
    // number of deletions required
    Console.WriteLine(minDeletions(str)) ;
  }
}
 
// This code is contributed by AnkThon

<script>
//Javascript program for
// the above approach
 
// Function to find the number of deletions
// required such that characters of the
// string can be rearranged to form a palindrome
function minDeletions(str)
{
    // Stores frequency of characters
    var fre = new Array(26);
    fre.fill(0);
 
    var n = str.length;
 
    // Store the frequency of each
    // character in frequency array
    for (var i = 0; i < n; i++) {
        //let a = parseInt(str[i] - 97);
        fre[str[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
         
    }
    var count = 0;
 
    // Count number of characters
    // with odd frequency
    for (var i = 0; i < 26; i++) {
        if (fre[i] % 2) {
            count += 1;
        }
    }
 
    // If count is 1 or 0, return 0
    if (count == 0 || count == 1) {
        return 0;
    }
 
    // Otherwise, return count - 1
    else {
        return count - 1;
    }
}
 
    var str = "ababbccca";
 
    // Function call to find minimum
    // number of deletions required
    document.write( minDeletions(str)+"<br>");
     
     
    // This code is contributed by SoumikMondal
</script>

2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)