Reorganiza los caracteres de la string dada para formar una primera string palindrómica lexicográficamente. Si no existe tal string, se muestra el mensaje «no hay string palindrómica». Ejemplos:
Input : malayalam Output : aalmymlaa Input : apple Output : no palindromic string
Enfoque simple: 1. Ordene los caracteres de string en orden alfabético (ascendente). 2. Uno debe encontrar lexicográficamente la siguiente permutación de la string dada. 3. La primera permutación que es palíndromo es la respuesta.
Enfoque eficiente: propiedades de la string palindrómica: 1. Si la longitud de la string es par, entonces la frecuencia de cada carácter de la string debe ser par. 2. Si la longitud es impar, debe haber un carácter cuya frecuencia sea impar y todos los demás caracteres deben tener una frecuencia par y al menos una ocurrencia del carácter impar debe estar presente en el medio de la string.
Algoritmo 1. Almacena la frecuencia de cada carácter en la string dada 2. Comprueba si una string palindrómica se puede formar o no usando las propiedades de la string palindrómica mencionadas anteriormente. 3. Si no se puede formar una string palindrómica, devuelva «Sin string palindrómica». 4. De lo contrario, creamos tres strings y luego devolvemos front_str + odd_str + rear_str.
- odd_str: está vacío si no hay ningún carácter con frecuencia impar. De lo contrario, contiene todas las apariciones de carácter impar.
- front_str : contiene la mitad de las ocurrencias de todos los caracteres pares de la string en orden creciente.
- rear_str Contiene la mitad de las apariciones de todos los caracteres pares de la string en orden inverso a front_str.
A continuación se muestra la implementación de los pasos anteriores.
C++
// C++ program to find first palindromic permutation
// of given string
#include <bits/stdc++.h>
using namespace std;
const char MAX_CHAR = 26;
// Function to count frequency of each char in the
// string. freq[0] for 'a',...., freq[25] for 'z'
void countFreq(string str, int freq[], int len)
{
for (int i=0; i<len; i++)
freq[str.at(i) - 'a']++;
}
// Cases to check whether a palindr0mic
// string can be formed or not
bool canMakePalindrome(int freq[], int len)
{
// count_odd to count no of
// chars with odd frequency
int count_odd = 0;
for (int i=0; i<MAX_CHAR; i++)
if (freq[i]%2 != 0)
count_odd++;
// For even length string
// no odd freq character
if (len%2 == 0)
{
if (count_odd > 0)
return false;
else
return true;
}
// For odd length string
// one odd freq character
if (count_odd != 1)
return false;
return true;
}
// Function to find odd freq char and
// reducing its freq by 1returns "" if odd freq
// char is not present
string findOddAndRemoveItsFreq(int freq[])
{
string odd_str = "";
for (int i=0; i<MAX_CHAR; i++)
{
if (freq[i]%2 != 0)
{
freq[i]--;
odd_str = odd_str + (char)(i+'a');
return odd_str;
}
}
return odd_str;
}
// To find lexicographically first palindromic
// string.
string findPalindromicString(string str)
{
int len = str.length();
int freq[MAX_CHAR] = {0};
countFreq(str, freq, len);
if (!canMakePalindrome(freq, len))
return "No Palindromic String";
// Assigning odd freq character if present
// else empty string.
string odd_str = findOddAndRemoveItsFreq(freq);
string front_str = "", rear_str = " ";
// Traverse characters in increasing order
for (int i=0; i<MAX_CHAR; i++)
{
string temp = "";
if (freq[i] != 0)
{
char ch = (char)(i + 'a');
// Divide all occurrences into two
// halves. Note that odd character
// is removed by findOddAndRemoveItsFreq()
for (int j=1; j<=freq[i]/2; j++)
temp = temp + ch;
// creating front string
front_str = front_str + temp;
// creating rear string
rear_str = temp + rear_str;
}
}
// Final palindromic string which is
// lexicographically first
return (front_str + odd_str + rear_str);
}
// Driver program
int main()
{
string str = "malayalam";
cout << findPalindromicString(str);
return 0;
}
Java
// Java program to find first palindromic permutation
// of given string
class GFG {
static char MAX_CHAR = 26;
// Function to count frequency of each char in the
// string. freq[0] for 'a',...., freq[25] for 'z'
static void countFreq(String str, int freq[], int len)
{
for (int i = 0; i < len; i++)
{
freq[str.charAt(i) - 'a']++;
}
}
// Cases to check whether a palindr0mic
// string can be formed or not
static boolean canMakePalindrome(int freq[], int len)
{
// count_odd to count no of
// chars with odd frequency
int count_odd = 0;
for (int i = 0; i < MAX_CHAR; i++)
{
if (freq[i] % 2 != 0)
{
count_odd++;
}
}
// For even length string
// no odd freq character
if (len % 2 == 0)
{
if (count_odd > 0)
{
return false;
}
else
{
return true;
}
}
// For odd length string
// one odd freq character
if (count_odd != 1)
{
return false;
}
return true;
}
// Function to find odd freq char and
// reducing its freq by 1returns "" if odd freq
// char is not present
static String findOddAndRemoveItsFreq(int freq[])
{
String odd_str = "";
for (int i = 0; i < MAX_CHAR; i++)
{
if (freq[i] % 2 != 0)
{
freq[i]--;
odd_str = odd_str + (char) (i + 'a');
return odd_str;
}
}
return odd_str;
}
// To find lexicographically first palindromic
// string.
static String findPalindromicString(String str)
{
int len = str.length();
int freq[] = new int[MAX_CHAR];
countFreq(str, freq, len);
if (!canMakePalindrome(freq, len))
{
return "No Palindromic String";
}
// Assigning odd freq character if present
// else empty string.
String odd_str = findOddAndRemoveItsFreq(freq);
String front_str = "", rear_str = " ";
// Traverse characters in increasing order
for (int i = 0; i < MAX_CHAR; i++)
{
String temp = "";
if (freq[i] != 0)
{
char ch = (char) (i + 'a');
// Divide all occurrences into two
// halves. Note that odd character
// is removed by findOddAndRemoveItsFreq()
for (int j = 1; j <= freq[i] / 2; j++)
{
temp = temp + ch;
}
// creating front string
front_str = front_str + temp;
// creating rear string
rear_str = temp + rear_str;
}
}
// Final palindromic string which is
// lexicographically first
return (front_str + odd_str + rear_str);
}
// Driver program
public static void main(String[] args)
{
String str = "malayalam";
System.out.println(findPalindromicString(str));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find first palindromic permutation
# of given string
MAX_CHAR = 26;
# Function to count frequency of each char in the
# string. freq[0] for 'a',...., freq[25] for 'z'
def countFreq(str1, freq, len1):
for i in range(len1):
freq[ord(str1[i]) - ord('a')] += 1;
# Cases to check whether a palindr0mic
# string can be formed or not
def canMakePalindrome(freq, len1):
# count_odd to count no of
# chars with odd frequency
count_odd = 0;
for i in range(MAX_CHAR):
if (freq[i] % 2 != 0):
count_odd += 1;
# For even length string
# no odd freq character
if (len1 % 2 == 0):
if (count_odd > 0):
return False;
else:
return True;
# For odd length string
# one odd freq character
if (count_odd != 1):
return False;
return True;
# Function to find odd freq char and
# reducing its freq by 1returns "" if odd freq
# char is not present
def findOddAndRemoveItsFreq(freq):
odd_str = "";
for i in range(MAX_CHAR):
if (freq[i]%2 != 0):
freq[i]-=1;
odd_str += chr(i+ord('a'));
return odd_str;
return odd_str;
# To find lexicographically first palindromic
# string.
def findPalindromicString(str1):
len1 = len(str1);
freq=[0]*MAX_CHAR;
countFreq(str1, freq, len1);
if (canMakePalindrome(freq, len1) == False):
return "No Palindromic String";
# Assigning odd freq character if present
# else empty string.
odd_str = findOddAndRemoveItsFreq(freq);
front_str = "";
rear_str = " ";
# Traverse characters in increasing order
for i in range(MAX_CHAR):
temp = "";
if (freq[i] != 0):
ch = chr(i + ord('a'));
# Divide all occurrences into two
# halves. Note that odd character
# is removed by findOddAndRemoveItsFreq()
for j in range(1,int(freq[i]/2)+1):
temp += ch;
# creating front string
front_str += temp;
# creating rear string
rear_str = temp+rear_str;
# Final palindromic string which is
# lexicographically first
return (front_str + odd_str+rear_str);
# Driver code
str1 = "malayalam";
print(findPalindromicString(str1));
# This code is contributed by mits
C#
// C# program to find first palindromic permutation
// of given string
using System;
class GFG
{
static int MAX_CHAR = 26;
// Function to count frequency of each char in the
// string. freq[0] for 'a',...., freq[25] for 'z'
static void countFreq(string str, int[] freq, int len)
{
for (int i = 0; i < len; i++)
{
freq[str[i] - 'a']++;
}
}
// Cases to check whether a palindr0mic
// string can be formed or not
static bool canMakePalindrome(int[] freq, int len)
{
// count_odd to count no of
// chars with odd frequency
int count_odd = 0;
for (int i = 0; i < MAX_CHAR; i++)
{
if (freq[i] % 2 != 0)
{
count_odd++;
}
}
// For even length string
// no odd freq character
if (len % 2 == 0)
{
if (count_odd > 0)
{
return false;
}
else
{
return true;
}
}
// For odd length string
// one odd freq character
if (count_odd != 1)
{
return false;
}
return true;
}
// Function to find odd freq char and
// reducing its freq by 1returns "" if odd freq
// char is not present
static string findOddAndRemoveItsFreq(int[] freq)
{
string odd_str = "";
for (int i = 0; i < MAX_CHAR; i++)
{
if (freq[i] % 2 != 0)
{
freq[i]--;
odd_str = odd_str + (char) (i + 'a');
return odd_str;
}
}
return odd_str;
}
// To find lexicographically first
// palindromic string.
static string findPalindromicString(string str)
{
int len = str.Length;
int[] freq = new int[MAX_CHAR];
countFreq(str, freq, len);
if (!canMakePalindrome(freq, len))
{
return "No Palindromic String";
}
// Assigning odd freq character if present
// else empty string.
string odd_str = findOddAndRemoveItsFreq(freq);
string front_str = "", rear_str = " ";
// Traverse characters in increasing order
for (int i = 0; i < MAX_CHAR; i++)
{
String temp = "";
if (freq[i] != 0)
{
char ch = (char) (i + 'a');
// Divide all occurrences into two
// halves. Note that odd character
// is removed by findOddAndRemoveItsFreq()
for (int j = 1; j <= freq[i] / 2; j++)
{
temp = temp + ch;
}
// creating front string
front_str = front_str + temp;
// creating rear string
rear_str = temp + rear_str;
}
}
// Final palindromic string which is
// lexicographically first
return (front_str + odd_str + rear_str);
}
// Driver code
public static void Main()
{
string str = "malayalam";
Console.Write(findPalindromicString(str));
}
}
// This code is contributed by Ita_c.
PHP
<?php
// PHP program to find first palindromic permutation
// of given string
$MAX_CHAR = 26;
// Function to count frequency of each char in the
// string. freq[0] for 'a',...., freq[25] for 'z'
function countFreq($str, &$freq, $len)
{
for ($i = 0; $i < $len; $i++)
$freq[ord($str[$i]) - ord('a')]++;
}
// Cases to check whether a palindr0mic
// string can be formed or not
function canMakePalindrome($freq, $len)
{
global $MAX_CHAR;
// count_odd to count no of
// chars with odd frequency
$count_odd = 0;
for ($i = 0; $i < $MAX_CHAR; $i++)
if ($freq[$i] % 2 != 0)
$count_odd++;
// For even length string
// no odd freq character
if ($len % 2 == 0)
{
if ($count_odd > 0)
return false;
else
return true;
}
// For odd length string
// one odd freq character
if ($count_odd != 1)
return false;
return true;
}
// Function to find odd freq char and
// reducing its freq by 1returns "" if odd freq
// char is not present
function findOddAndRemoveItsFreq($freq)
{
global $MAX_CHAR;
$odd_str = "";
for ($i = 0; $i < $MAX_CHAR; $i++)
{
if ($freq[$i] % 2 != 0)
{
$freq[$i]--;
$odd_str .= chr($i+ord('a'));
return $odd_str;
}
}
return $odd_str;
}
// To find lexicographically first palindromic
// string.
function findPalindromicString($str)
{
global $MAX_CHAR;
$len = strlen($str);
$freq=array_fill(0, $MAX_CHAR, 0);
countFreq($str, $freq, $len);
if (!canMakePalindrome($freq, $len))
return "No Palindromic String";
// Assigning odd freq character if present
// else empty string.
$odd_str = findOddAndRemoveItsFreq($freq);
$front_str = "";
$rear_str = " ";
// Traverse characters in increasing order
for ($i = 0; $i < $MAX_CHAR; $i++)
{
$temp = "";
if ($freq[$i] != 0)
{
$ch = chr($i + ord('a'));
// Divide all occurrences into two
// halves. Note that odd character
// is removed by findOddAndRemoveItsFreq()
for ($j = 1; $j <= (int)($freq[$i]/2); $j++)
$temp .= $ch;
// creating front string
$front_str .= $temp;
// creating rear string
$rear_str = $temp.$rear_str;
}
}
// Final palindromic string which is
// lexicographically first
return ($front_str.$odd_str.$rear_str);
}
// Driver code
$str = "malayalam";
echo findPalindromicString($str);
// This code is contributed by mits
?>
Producción
aalmymlaa
Complejidad de tiempo: O (n) donde n es la longitud de la string de entrada. Suponiendo que el tamaño del alfabeto de string es constante. Este artículo es una contribución de Ayush Jauhari . 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA