Eliminación mínima de caracteres requerida de modo que la permutación de una string dada sea un palíndromo

Dada la string str que consta de letras minúsculas, la tarea es encontrar el número mínimo de caracteres que se eliminarán de la string dada de modo que cualquier permutación de la string restante sea un palíndromo .

Ejemplos:

Entrada: str=”aba”
Salida: 1
Explicación: Eliminar ‘b’ genera una string palindrómica “aa”.

Entrada: “abab”
Salida: 0
Explicación: Las permutaciones “abba”, “baab” de la string dada ya son palíndromos. Por lo tanto, no es necesario eliminar ningún carácter.

Entrada: “abab”
Salida: 0

Enfoque: siga los pasos a continuación para resolver el problema:

1. Compruebe si la string dada ya es un palíndromo o no . Si se encuentra que es cierto, imprima 0 .
2. De lo contrario, calcule la frecuencia de cada carácter en la string usando un Hashmap .
3. Cuente el número de caracteres con frecuencias impares y guárdelo en una variable, digamos k .
4. Ahora, la cantidad total de caracteres necesarios para eliminar es k-1 . Por lo tanto, imprima k – 1 como la respuesta requerida.

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 check if a string
// is palindrome or not
bool IsPalindrome(string& str)
{
    string s = str;
 
    // Reverse the string
    reverse(str.begin(), str.end());
 
    // Check if the string is
    // already a palindrome or not
    if (s == str) {
 
        return true;
    }
 
    return false;
}
 
// Function to calculate the minimum
// deletions to make a string palindrome
void CountDeletions(string& str, int len)
{
    if (IsPalindrome(str)) {
 
        cout << 0 << endl;
        return;
    }
 
    // Stores the frequencies
    // of each character
    map<char, int> mp;
 
    // Iterate over the string
    for (int i = 0; i < len; i++) {
 
        // Update frequency of
        // each character
        mp[str[i]]++;
    }
 
    int k = 0;
 
    // Iterate over the map
    for (auto it : mp) {
 
        // Count characters with
        // odd frequencies
        if (it.second & 1) {
            k++;
        }
    }
 
    // Print the result
    cout << k - 1 << endl;
}
 
int main()
{
    string str = "abca";
    int len = str.length();
    CountDeletions(str, len);
}

// Java program for the
// above approach
import java.util.*;
class GFG{
   
static String str;
 
static String reverse(String input)
{
  char[] a = input.toCharArray();
  int l, r = a.length - 1;
   
  for (l = 0; l < r; l++, r--)
  {
    char temp = a[l];
    a[l] = a[r];
    a[r] = temp;
  }
  return String.valueOf(a);
}
   
// Function to check if a String
// is palindrome or not
static boolean IsPalindrome()
{
  String s = str;
 
  // Reverse the String
  s = reverse(str);
 
  // Check if the String is
  // already a palindrome or not
  if (s == str)
  {
    return true;
  }
 
  return false;
}
 
// Function to calculate the
// minimum deletions to make
// a String palindrome
static void CountDeletions(int len)
{
  if (IsPalindrome())
  {
    System.out.print(0 + "\n");
    return;
  }
 
  // Stores the frequencies
  // of each character
  HashMap<Character,
          Integer> mp =
          new HashMap<>();
 
  // Iterate over the String
  for (int i = 0; i < len; i++)
  {
    // Update frequency of
    // each character
    if(mp.containsKey(str.charAt(i)))
    {
      mp.put(str.charAt(i),
      mp.get(str.charAt(i)) + 1);
    }
    else
    {
      mp.put(str.charAt(i), 1);
    }
  }
 
  int k = 0;
 
  // Iterate over the map
  for (Map.Entry<Character,
                 Integer> it :
       mp.entrySet())
  {
    // Count characters with
    // odd frequencies
    if (it.getValue() % 2 == 1)
    {
      k++;
    }
  }
 
  // Print the result
  System.out.print(k - 1 + "\n");
}
 
// Driver code
public static void main(String[] args)
{
  str = "abca";
  int len = str.length();
  CountDeletions(len);
}
}
 
// This code is contributed by gauravrajput1

# Python3 program for the above approach
from collections import defaultdict
 
# Function to check if a string
# is palindrome or not
def IsPalindrome(str):
     
    s = str
 
    # Reverse the string
    s = s[::-1]
 
    # Check if the string is
    # already a palindrome or not
    if (s == str):
        return True
 
    return False
 
# Function to calculate the minimum
# deletions to make a string palindrome
def CountDeletions(str, ln):
 
    if (IsPalindrome(str)):
        print(0)
        return
 
    # Stores the frequencies
    # of each character
    mp = defaultdict(lambda : 0)
 
    # Iterate over the string
    for i in range(ln):
         
        # Update frequency of
        # each character
        mp[str[i]] += 1
 
    k = 0
 
    # Iterate over the map
    for it in mp.keys():
         
        # Count characters with
        # odd frequencies
        if (mp[it] & 1):
            k += 1
 
    # Print the result
    print(k - 1)
 
# Driver code
if __name__ == '__main__':
 
    str = "abca"
 
    ln = len(str)
 
    # Function Call
    CountDeletions(str, ln)
 
# This code is contributed by Shivam Singh

// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
   
static String str;
 
static String reverse(String input)
{
  char[] a = input.ToCharArray();
  int l, r = a.Length - 1;
   
  for (l = 0; l < r; l++, r--)
  {
    char temp = a[l];
    a[l] = a[r];
    a[r] = temp;
  }
  return String.Join("", a);
}
   
// Function to check if
// a String is palindrome 
// or not
static bool IsPalindrome()
{
  String s = str;
 
  // Reverse the String
  s = reverse(str);
 
  // Check if the String
  // is already a palindrome
  // or not
  if (s == str)
  {
    return true;
  }
 
  return false;
}
 
// Function to calculate the
// minimum deletions to make
// a String palindrome
static void CountDeletions(int len)
{
  if (IsPalindrome())
  {
    Console.Write(0 + "\n");
    return;
  }
 
  // Stores the frequencies
  // of each character
  Dictionary<char,
             int> mp =
             new Dictionary<char,
                            int>();
 
  // Iterate over the String
  for (int i = 0; i < len; i++)
  {
    // Update frequency of
    // each character
    if(mp.ContainsKey(str[i]))
    {
      mp[str[i]] = mp[str[i]] + 1;
    }
    else
    {
      mp.Add(str[i], 1);
    }
  }
 
  int k = 0;
 
  // Iterate over the map
  foreach (KeyValuePair<char,
                        int> it in mp)
  {
    // Count characters with
    // odd frequencies
    if (it.Value % 2 == 1)
    {
      k++;
    }
  }
 
  // Print the result
  Console.Write(k - 1 + "\n");
}
 
// Driver code
public static void Main(String[] args)
{
  str = "abca";
  int len = str.Length;
  CountDeletions(len);
}
}
 
// This code is contributed by Princi Singh

<script>
    // Javascript program for the above approach
     
    let str;
  
    function reverse(input)
    {
      let a = input.split('');
      let l, r = a.length - 1;
 
      for (l = 0; l < r; l++, r--)
      {
        let temp = a[l];
        a[l] = a[r];
        a[r] = temp;
      }
      return a.join("");
    }
 
    // Function to check if
    // a String is palindrome
    // or not
    function IsPalindrome()
    {
      let s = str;
 
      // Reverse the String
      s = reverse(str);
 
      // Check if the String
      // is already a palindrome
      // or not
      if (s == str)
      {
        return true;
      }
 
      return false;
    }
 
    // Function to calculate the
    // minimum deletions to make
    // a String palindrome
    function CountDeletions(len)
    {
      if (IsPalindrome())
      {
        document.write(0 + "</br>");
        return;
      }
 
      // Stores the frequencies
      // of each character
      let mp = new Map();
 
      // Iterate over the String
      for (let i = 0; i < len; i++)
      {
        // Update frequency of
        // each character
        if(mp.has(str[i]))
        {
          mp.set(str[i], mp.get(str[i]) + 1);
        }
        else
        {
          mp.set(str[i], 1);
        }
      }
 
      let k = 0;
 
      // Iterate over the map
      mp.forEach((values,it)=>{
        if(values % 2 == 1)
        {
            k++;
        }
      })
 
      // Print the result
      document.write((k - 1) + "</br>");
    }
     
    str = "abca";
    let len = str.length;
    CountDeletions(len);
 
</script>

1

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