Inserciones mínimas para formar un palíndromo con permutaciones permitidas

Dada una string de letras minúsculas. Encuentre los caracteres mínimos que se insertarán en la string para que pueda convertirse en palíndromo. Podemos cambiar las posiciones de los caracteres en la string.

Ejemplos: 

Input : geeksforgeeks
Output : 2
geeksforgeeks can be changed as:
geeksroforskeeg
geeksorfroskeeg
and many more

Input : aabbc
Output : 0
aabbc can be changed as:
abcba
bacab

Una string palindrómica puede tener un carácter impar solo cuando la longitud de la string es impar; de lo contrario, todos los caracteres aparecen un número par de veces. Entonces, tenemos que encontrar caracteres que ocurren en momentos extraños en una string.

La idea es contar la aparición de cada carácter en una string. Como la string palindrómica puede tener un carácter que aparece en ocasiones impares, el número de inserciones será uno menos que el número de caracteres que aparecen en ocasiones impares. Y si la string ya es palíndromo, no necesitamos añadir ningún carácter, por lo que el resultado será 0. 

Implementación:

// CPP program to find minimum number
// of insertions to make a string
// palindrome
#include <bits/stdc++.h>
using namespace std;
 
// Function will return number of
// characters to be added
int minInsertion(string str)
{
    // To store string length
    int n = str.length();
 
    // To store number of characters
    // occurring odd number of times
    int res = 0;
 
    // To store count of each
    // character
    int count[26] = { 0 };
 
    // To store occurrence of each
    // character
    for (int i = 0; i < n; i++)
        count[str[i] - 'a']++;
 
    // To count characters with odd
    // occurrence
    for (int i = 0; i < 26; i++)
        if (count[i] % 2 == 1)
            res++;
 
    // As one character can be odd return
    // res - 1 but if string is already
    // palindrome return 0
    return (res == 0) ? 0 : res - 1;
}
 
// Driver program
int main()
{
    string str = "geeksforgeeks";
    cout << minInsertion(str);
 
    return 0;
}

// Java program to find minimum number
// of insertions to make a string
// palindrome
public class Palindrome {
 
    // Function will return number of
    // characters to be added
    static int minInsertion(String str)
    {
        // To store string length
        int n = str.length();
 
        // To store number of characters
        // occurring odd number of times
        int res = 0;
 
        // To store count of each
        // character
        int[] count = new int[26];
 
        // To store occurrence of each
        // character
        for (int i = 0; i < n; i++)
            count[str.charAt(i) - 'a']++;
 
        // To count characters with odd
        // occurrence
        for (int i = 0; i < 26; i++) {
            if (count[i] % 2 == 1)
                res++;
        }
 
        // As one character can be odd return
        // res - 1 but if string is already
        // palindrome return 0
        return (res == 0) ? 0 : res - 1;
    }
 
    // Driver program
    public static void main(String[] args)
    {
        String str = "geeksforgeeks";
        System.out.println(minInsertion(str));
    }
}

# Python3 program to find minimum number
# of insertions to make a string
# palindrome
import math as mt
 
# Function will return number of
# characters to be added
def minInsertion(tr1):
 
    # To store string length
    n = len(str1)
 
    # To store number of characters
    # occurring odd number of times
    res = 0
 
    # To store count of each
    # character
    count = [0 for i in range(26)]
 
    # To store occurrence of each
    # character
    for i in range(n):
        count[ord(str1[i]) - ord('a')] += 1
 
    # To count characters with odd
    # occurrence
    for i in range(26):
        if (count[i] % 2 == 1):
            res += 1
 
    # As one character can be odd return
    # res - 1 but if string is already
    # palindrome return 0
    if (res == 0):
        return 0
    else:
        return res - 1
 
# Driver Code
str1 = "geeksforgeeks"
print(minInsertion(str1))
 
# This code is contributed by
# Mohit kumar 29

// C# program to find minimum number
// of insertions to make a string
// palindrome
using System;
 
public class GFG {
 
    // Function will return number of
    // characters to be added
    static int minInsertion(String str)
    {
         
        // To store string length
        int n = str.Length;
 
        // To store number of characters
        // occurring odd number of times
        int res = 0;
 
        // To store count of each
        // character
        int[] count = new int[26];
 
        // To store occurrence of each
        // character
        for (int i = 0; i < n; i++)
            count[str[i] - 'a']++;
 
        // To count characters with odd
        // occurrence
        for (int i = 0; i < 26; i++) {
            if (count[i] % 2 == 1)
                res++;
        }
 
        // As one character can be odd
        // return res - 1 but if string
        // is already palindrome
        // return 0
        return (res == 0) ? 0 : res - 1;
    }
 
    // Driver program
    public static void Main()
    {
        string str = "geeksforgeeks";
         
        Console.WriteLine(minInsertion(str));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find minimum number
// of insertions to make a string
// palindrome
 
// Function will return number of
// characters to be added
function minInsertion($str)
{
    // To store string length
    $n = strlen($str);
 
    // To store number of characters
    // occurring odd number of times
    $res = 0;
 
    // To store count of each
    // character
    $count = array(26);
 
    // To store occurrence of each
    // character
    for ($i = 0; $i < $n; $i++)
        $count[ord($str[$i]) - ord('a')]++;
 
    // To count characters with odd
    // occurrence
    for ($i = 0; $i < 26; $i++)
    {
        if ($count[$i] % 2 == 1)
            $res++;
    }
 
    // As one character can be odd return
    // res - 1 but if string is already
    // palindrome return 0
    return ($res == 0) ? 0 : $res - 1;
}
 
// Driver program
$str = "geeksforgeeks";
echo(minInsertion($str));
 
// This code is contributed
// by Mukul Singh
?>

<script>
 
// JavaScript program to find minimum number
// of insertions to make a string
// palindrome
     
    // Function will return number of
    // characters to be added
    function minInsertion(str)
    {
        // To store string length
        let n = str.length;
   
        // To store number of characters
        // occurring odd number of times
        let res = 0;
   
        // To store count of each
        // character
        let count = new Array(26);
        for(let i=0;i<count.length;i++)
        {
            count[i]=0;
        }
   
        // To store occurrence of each
        // character
        for (let i = 0; i < n; i++)
            count[str[i].charCodeAt(0) -
            'a'.charCodeAt(0)]++;
   
        // To count characters with odd
        // occurrence
        for (let i = 0; i < 26; i++) {
            if (count[i] % 2 == 1)
                res++;
        }
   
        // As one character can be odd return
        // res - 1 but if string is already
        // palindrome return 0
        return (res == 0) ? 0 : res - 1;
    }
     
    // Driver program
    let str = "geeksforgeeks";
    document.write(minInsertion(str));
     
 
// This code is contributed by unknown2108
 
</script>

2

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

Este artículo es una contribución de nuclode . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.