Dada una string, cuente cuántos palíndromos de longitud máxima están presentes. (No es necesario que sea una substring)
Ejemplos:
Input : str = "ababa" Output: 2 Explanation : palindromes of maximum of lengths are : "ababa", "baaab" Input : str = "ababab" Output: 4 Explanation : palindromes of maximum of lengths are : "ababa", "baaab", "abbba", "babab"
Enfoque Un palíndromo se puede representar como “str + t + reverse(str)” .
Nota : «t» está vacío para strings palindrómicas de longitud uniforme
. Calcule de cuántas maneras se puede hacer «str» y luego multiplíquelo con «t» (número de caracteres individuales omitidos).
Sea c i el número de ocurrencias de un carácter en la string. Considere los siguientes casos:
1. Si c i es par. Entonces la mitad de cada palíndromo máximo contendrá exactamente letras f i = c i / 2.
2.Si c i es impar. Entonces la mitad de cada palíndromo máximo contendrá exactamente letras f i = (c i – 1)/ 2.
Sea k el número de impares c i. Si k=0, la longitud del palíndromo máximo será par; de lo contrario, será impar y habrá exactamente k letras intermedias posibles, es decir, podemos colocar esta letra en el centro del palíndromo.
¡ El número de permutaciones de n objetos con n 1 objetos idénticos de tipo 1, n 2 objetos idénticos de tipo 2 y n3 objetos idénticos de tipo 3 es n! / (n1! * n2! * n3!) .
Así que aquí tenemos el número total de caracteres como f a +f b +f a +…….+f y +f z . Así que el número de permutaciones es (f a +f b +f a +…….+f y +fz )! / fa ! f b !…f y !f z !.
Ahora bien, si K no es 0, es obvio que la respuesta es k * (f a +f b +f a +…….+f y +f z +)! /fa ! f b !…f y !f z !
A continuación se muestra la implementación de lo anterior.
C++
// C++ implementation for counting
// maximum length palindromes
#include <bits/stdc++.h>
using namespace std;
// factorial of a number
int fact(int n)
{
int ans = 1;
for (int i = 1; i <= n; i++)
ans = ans * i;
return (ans);
}
// function to count maximum length palindromes.
int numberOfPossiblePalindrome(string str, int n)
{
// Count number of occurrence
// of a charterer in the string
unordered_map<char, int> mp;
for (int i = 0; i < n; i++)
mp[str[i]]++;
int k = 0; // Count of singles
int num = 0; // numerator of result
int den = 1; // denominator of result
int fi;
for (auto it = mp.begin(); it != mp.end(); ++it)
{
// if frequency is even
// fi = ci / 2
if (it->second % 2 == 0)
fi = it->second / 2;
// if frequency is odd
// fi = ci - 1 / 2.
else
{
fi = (it->second - 1) / 2;
k++;
}
// sum of all frequencies
num = num + fi;
// product of factorial of
// every frequency
den = den * fact(fi);
}
// if all character are unique
// so there will be no palindrome,
// so if num != 0 then only we are
// finding the factorial
if (num != 0)
num = fact(num);
int ans = num / den;
if (k != 0)
{
// k are the single
// elements that can be
// placed in middle
ans = ans * k;
}
return (ans);
}
// Driver program
int main()
{
char str[] = "ababab";
int n = strlen(str);
cout << numberOfPossiblePalindrome(str, n);
return 0;
}
Java
// Java implementation for counting
// maximum length palindromes
import java.util.*;
class GFG
{
// factorial of a number
static int fact(int n)
{
int ans = 1;
for (int i = 1; i <= n; i++)
ans = ans * i;
return (ans);
}
// function to count maximum length palindromes.
static int numberOfPossiblePalindrome(String str, int n)
{
// Count number of occurrence
// of a charterer in the string
Map<Character,Integer> mp = new HashMap<>();
for (int i = 0; i < n; i++)
mp.put( str.charAt(i),mp.get( str.charAt(i))==null?
1:mp.get( str.charAt(i))+1);
int k = 0; // Count of singles
int num = 0; // numerator of result
int den = 1; // denominator of result
int fi;
for (Map.Entry<Character,Integer> it : mp.entrySet())
{
// if frequency is even
// fi = ci / 2
if (it.getValue() % 2 == 0)
fi = it.getValue() / 2;
// if frequency is odd
// fi = ci - 1 / 2.
else
{
fi = (it.getValue() - 1) / 2;
k++;
}
// sum of all frequencies
num = num + fi;
// product of factorial of
// every frequency
den = den * fact(fi);
}
// if all character are unique
// so there will be no palindrome,
// so if num != 0 then only we are
// finding the factorial
if (num != 0)
num = fact(num);
int ans = num / den;
if (k != 0)
{
// k are the single
// elements that can be
// placed in middle
ans = ans * k;
}
return (ans);
}
// Driver code
public static void main(String[] args)
{
String str = "ababab";
int n = str.length();
System.out.println(numberOfPossiblePalindrome(str, n));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation for counting # maximum length palindromes import math as mt # factorial of a number def fact(n): ans = 1 for i in range(1, n + 1): ans = ans * i return (ans) # function to count maximum length palindromes. def numberOfPossiblePalindrome(string, n): # Count number of occurrence # of a charterer in the string mp = dict() for i in range(n): if string[i] in mp.keys(): mp[string[i]] += 1 else: mp[string[i]] = 1 k = 0 # Count of singles num = 0 # numerator of result den = 1 # denominator of result fi = 0 for it in mp: # if frequency is even # fi = ci / 2 if (mp[it] % 2 == 0): fi = mp[it] // 2 # if frequency is odd # fi = ci - 1 / 2. else: fi = (mp[it] - 1) // 2 k += 1 # sum of all frequencies num = num + fi # product of factorial of # every frequency den = den * fact(fi) # if all character are unique # so there will be no palindrome, # so if num != 0 then only we are # finding the factorial if (num != 0): num = fact(num) ans = num //den if (k != 0): # k are the single # elements that can be # placed in middle ans = ans * k return (ans) # Driver Code string = "ababab" n = len(string) print(numberOfPossiblePalindrome(string, n)) # This code is contributed by # Mohit kumar 29
C#
// C# implementation for counting
// maximum length palindromes
using System;
using System.Collections.Generic;
class GFG
{
// factorial of a number
static int fact(int n)
{
int ans = 1;
for (int i = 1; i <= n; i++)
ans = ans * i;
return (ans);
}
// function to count maximum length palindromes.
static int numberOfPossiblePalindrome(String str, int n)
{
// Count number of occurrence
// of a charterer in the string
Dictionary<char,int> mp = new Dictionary<char,int>();
for (int i = 0 ; i < n; i++)
{
if(mp.ContainsKey(str[i]))
{
var val = mp[str[i]];
mp.Remove(str[i]);
mp.Add(str[i], val + 1);
}
else
{
mp.Add(str[i], 1);
}
}
int k = 0; // Count of singles
int num = 0; // numerator of result
int den = 1; // denominator of result
int fi;
foreach(KeyValuePair<char, int> it in mp)
{
// if frequency is even
// fi = ci / 2
if (it.Value % 2 == 0)
fi = it.Value / 2;
// if frequency is odd
// fi = ci - 1 / 2.
else
{
fi = (it.Value - 1) / 2;
k++;
}
// sum of all frequencies
num = num + fi;
// product of factorial of
// every frequency
den = den * fact(fi);
}
// if all character are unique
// so there will be no palindrome,
// so if num != 0 then only we are
// finding the factorial
if (num != 0)
num = fact(num);
int ans = num / den;
if (k != 0)
{
// k are the single
// elements that can be
// placed in middle
ans = ans * k;
}
return (ans);
}
// Driver code
public static void Main(String[] args)
{
String str = "ababab";
int n = str.Length;
Console.WriteLine(numberOfPossiblePalindrome(str, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation for counting
// maximum length palindromes
// factorial of a number
function fact(n)
{
let ans = 1;
for (let i = 1; i <= n; i++)
ans = ans * i;
return (ans);
}
// function to count maximum length palindromes.
function numberOfPossiblePalindrome(str,n)
{
// Count number of occurrence
// of a charterer in the string
let mp = new Map();
for (let i = 0; i < n; i++)
mp.set( str[i],mp.get( str[i])==null?
1:mp.get( str[i])+1);
let k = 0; // Count of singles
let num = 0; // numerator of result
let den = 1; // denominator of result
let fi;
for (let [key, value] of mp.entries())
{
// if frequency is even
// fi = ci / 2
if (value % 2 == 0)
fi = value / 2;
// if frequency is odd
// fi = ci - 1 / 2.
else
{
fi = (value - 1) / 2;
k++;
}
// sum of all frequencies
num = num + fi;
// product of factorial of
// every frequency
den = den * fact(fi);
}
// if all character are unique
// so there will be no palindrome,
// so if num != 0 then only we are
// finding the factorial
if (num != 0)
num = fact(num);
let ans = Math.floor(num / den);
if (k != 0)
{
// k are the single
// elements that can be
// placed in middle
ans = ans * k;
}
return (ans);
}
// Driver code
let str = "ababab";
let n = str.length;
document.write(numberOfPossiblePalindrome(str, n));
// This code is contributed by unknown2108
</script>
Producción:
4
Complejidad de tiempo : O(n)
Publicación traducida automáticamente
Artículo escrito por Bibhu Pala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA