Dada la string str, encuentre el recuento de todas las permutaciones palindrómicas de la misma.
Ejemplos:
Input : str = "gfgf" Output : 2 There are two palindromic permutations fggf and gffg Input : str = "abc" Output : 0
La idea se basa en los siguientes hechos:
- Una string puede permutarse a un palíndromo si el número de caracteres impares es como máximo uno.
- Una ocurrencia del único carácter impar siempre va al medio.
- La mitad de los recuentos de todos los personajes deciden el resultado. En caso de que ocurra un carácter impar, es piso de la mitad. La otra mitad se decide automáticamente.
Por ejemplo, si la string de entrada es «aabbccd», ¡el recuento de permutaciones palindrómicas es 3! (Obtenemos tres tomando la palabra de la mitad de todos los recuentos)
¿Qué sucede si la mitad misma tiene caracteres repetidos?
Aplicamos una regla combinatoria simple y dividimos por factorial de la mitad.
Por ejemplo “aaaaaabbbb”, el piso de la mitad de la string es 5. En la mitad de una string palindrómica, ‘a’ se repite tres veces y ‘b’ se repite dos veces, por lo que nuestro resultado es (5!) / (2!) * (3!).
C++
// CPP program to find number of
// palindromic permutations of a
// given string
#include <bits/stdc++.h>
using namespace std;
const int MAX = 256;
// Returns factorial of n
long long int fact(int n)
{
long long int res = 1;
for (int i = 2; i <= n; i++)
res = res * i;
return res;
}
// Returns count of palindromic
// permutations of str.
int countPalinPermutations(string &str)
{
// Count frequencies of all characters
int n = str.length();
int freq[MAX] = { 0 };
for (int i = 0; i < n; i++)
freq[str[i]]++;
// Since half of the characters
// decide count of palindromic
// permutations, we take (n/2)!
long long int res = fact(n / 2);
// To make sure that there is at
// most one odd occurring char
bool oddFreq = false;
// Traverse through all counts
for (int i = 0; i < MAX; i++) {
int half = freq[i] / 2;
// To make sure that the
// string can permute to
// form a palindrome
if (freq[i] % 2 != 0) {
// If there are more than
// one odd occurring chars
if (oddFreq == true)
return 0;
oddFreq = true;
}
// Divide all permutations with
// repeated characters
res = res / fact(half);
}
return res;
}
// Driver code
int main()
{
string str = "gffg";
cout << countPalinPermutations(str);
return 0;
}
Java
// Java program to find number of
// palindromic permutations of a
// given string
class GFG {
static final int MAX = 256;
// Returns factorial of n
static long fact(int n)
{
long res = 1;
for (int i = 2; i <= n; i++)
res = res * i;
return res;
}
// Returns count of palindromic
// permutations of str.
static int countPalinPermutations(String str)
{
// Count frequencies of all characters
int n = str.length();
int freq[]=new int[MAX];
for (int i = 0; i < n; i++)
freq[str.charAt(i)]++;
// Since half of the characters
// decide count of palindromic
// permutations, we take (n/2)!
long res = fact(n / 2);
// To make sure that there is at
// most one odd occurring char
boolean oddFreq = false;
// Traverse through all counts
for (int i = 0; i < MAX; i++) {
int half = freq[i] / 2;
// To make sure that the
// string can permute to
// form a palindrome
if (freq[i] % 2 != 0) {
// If there are more than
// one odd occurring chars
if (oddFreq == true)
return 0;
oddFreq = true;
}
// Divide all permutations with
// repeated characters
res = res / fact(half);
}
return (int)res;
}
// Driver code
public static void main (String[] args)
{
String str = "gffg";
System.out.print(
countPalinPermutations(str));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find number of # palindromic permutations of a # given string MAX = 256 # Returns factorial of n def fact(n) : res = 1 for i in range(2, n+1) : res = res * i return res # Returns count of palindromic # permutations of str. def countPalinPermutations(str) : global MAX # Count frequencies of # all characters n = len(str) freq = [0] * MAX; for i in range(0, n) : freq[ord(str[i])] = freq[ord(str[i])] + 1; # Since half of the characters # decide count of palindromic # permutations, we take (n/2)! res = fact(int(n / 2)) # To make sure that there is at # most one odd occurring char oddFreq = False # Traverse through all counts for i in range(0, MAX) : half = int(freq[i] / 2) # To make sure that the # string can permute to # form a palindrome if (freq[i] % 2 != 0): # If there are more than # one odd occurring chars if (oddFreq == True): return 0 oddFreq = True # Divide all permutations # with repeated characters res = int(res / fact(half)) return res # Driver code str = "gffg" print (countPalinPermutations(str)) # This code is contributed by Manish Shaw # (manishshaw1)
C#
// C# program to find number of
// palindromic permutations of a
// given string
using System;
class GFG {
static int MAX = 256;
// Returns factorial of n
static long fact(int n)
{
long res = 1;
for (int i = 2; i <= n; i++)
res = res * i;
return res;
}
// Returns count of palindromic
// permutations of str.
static int countPalinPermutations(string str)
{
// Count frequencies of all characters
int n = str.Length;
int []freq=new int[MAX];
for (int i = 0; i < n; i++)
freq[str[i]]++;
// Since half of the characters
// decide count of palindromic
// permutations, we take (n/2)!
long res = fact(n / 2);
// To make sure that there is at
// most one odd occurring char
bool oddFreq = false;
// Traverse through all counts
for (int i = 0; i < MAX; i++) {
int half = freq[i] / 2;
// To make sure that the
// string can permute to
// form a palindrome
if (freq[i] % 2 != 0) {
// If there are more than
// one odd occurring chars
if (oddFreq == true)
return 0;
oddFreq = true;
}
// Divide all permutations with
// repeated characters
res = res / fact(half);
}
return (int)res;
}
// Driver code
public static void Main ()
{
string str = "gffg";
Console.WriteLine(
countPalinPermutations(str));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find number of
// palindromic permutations of a
// given string
$MAX = 256;
// Returns factorial of n
function fact($n)
{
$res = 1;
for ($i = 2; $i <= $n; $i++)
$res = $res * $i;
return $res;
}
// Returns count of palindromic
// permutations of str.
function countPalinPermutations(&$str)
{
global $MAX ;
// Count frequencies of
// all characters
$n = strlen($str);
$freq = (0);
for ($i = 0; $i < $n; $i++)
// Since half of the characters
// decide count of palindromic
// permutations, we take (n/2)!
$res = fact($n / 2);
// To make sure that there is at
// most one odd occurring char
$oddFreq = false;
// Traverse through all counts
for ($i = 0; $i < $MAX; $i++)
{
$half = $freq[$i] / 2;
// To make sure that the
// string can permute to
// form a palindrome
if ($freq[$i] % 2 != 0)
{
// If there are more than
// one odd occurring chars
if ($oddFreq == true)
return 0;
$oddFreq = true;
}
// Divide all permutations
// with repeated characters
$res = $res / fact($half);
}
return $res;
}
// Driver code
$str = "gffg";
echo countPalinPermutations($str);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find number of
// palindromic permutations of a
// given string
let MAX = 256;
// Returns factorial of n
function fact(n)
{
let res = 1;
for (let i = 2; i <= n; i++)
res = res * i;
return res;
}
// Returns count of palindromic
// permutations of str.
function countPalinPermutations(str)
{
// Count frequencies of all characters
let n = str.length;
let freq = new Array(MAX);
freq.fill(0);
for (let i = 0; i < n; i++)
freq[str[i].charCodeAt()]++;
// Since half of the characters
// decide count of palindromic
// permutations, we take (n/2)!
let res = fact(n / 2);
// To make sure that there is at
// most one odd occurring char
let oddFreq = false;
// Traverse through all counts
for (let i = 0; i < MAX; i++) {
let half = freq[i] / 2;
// To make sure that the
// string can permute to
// form a palindrome
if (freq[i] % 2 != 0) {
// If there are more than
// one odd occurring chars
if (oddFreq == true)
return 0;
oddFreq = true;
}
// Divide all permutations with
// repeated characters
res = res / fact(half);
}
return res;
}
let str = "gffg";
document.write(countPalinPermutations(str));
</script>
Producción :
2
La solución anterior provoca el desbordamiento muy pronto. Podemos evitar el desbordamiento haciendo aritmética modular. En el próximo artículo, discutiremos el enfoque modular basado en la aritmética.