Dada la string str , la tarea es reorganizar la string dada para obtener la substring palindrómica más larga .
Ejemplos:
Entrada: str = “geeksforgeeks”
Salida: eegksfskgeeor
Explicación: eegksfskgee es la substring palindrómica más larga después de reorganizar la string.
Por lo tanto, la salida requerida es eegksfskgeeor.Entrada: str = «ingeniería»
Salida: eginenigenr
Enfoque: El problema se puede resolver usando Hashing . La idea es contar la frecuencia de cada carácter de la string dada . Si el recuento de ocurrencias de un carácter excede 1, agregue la mitad (valor mínimo) de su frecuencia en el lado izquierdo de la string resultante y la mitad restante en el lado derecho de la string resultante. Para los caracteres restantes, agregue un carácter en el medio de la string resultante y el resto al principio o al final de la string resultante. Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos hash[256] para almacenar la frecuencia de cada carácter .
- Para agregar de manera eficiente los caracteres en ambos lados de la string resultante, inicialice tres strings res1, res2 y res3 .
- La string res1 almacena la mitad izquierda de la substring palindrómica más larga posible, res2 almacena la mitad derecha de la substring palindrómica más larga posible y res3 almacena los caracteres restantes.
- Recorra la array hash[] y para el carácter, digamos hash[i] , verifique si su frecuencia es mayor que 1 o no. Si se determina que es cierto, agregue el carácter floor(hash[i]/2) veces en res1 y floor(hash[i]/2) veces en res2 .
- De lo contrario, agregue el primer carácter para no cumplir la condición anterior a res1 y todos los caracteres restantes a res3 .
- Finalmente, devuelve la string res1 + reverse(res2) + res3 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to rearrange the string to
// get the longest palindromic substring
string longestPalinSub(string str) {
// Stores the length of str
int N = str.length();
// Store the count of occurrence
// of each character
int hash[256] = {0};
// Traverse the string, str
for(int i = 0; i < N;
i++) {
// Count occurrence of
// each character
hash[str[i]]++;
}
// Store the left half of the
// longest palindromic substring
string res1 = "";
// Store the right half of the
// longest palindromic substring
string res2 = "";
// Traverse the array, hash[]
for(int i = 0; i< 256; i++) {
// Append half of the
// characters to res1
for(int j = 0; j < hash[i] / 2;
j++) {
res1.push_back(i);
}
// Append half of the
// characters to res2
for(int j = (hash[i] + 1)/2;
j < hash[i]; j++) {
res2.push_back(i);
}
}
// reverse string res2 to make
// res1 + res2 palindrome
reverse(res2.begin(), res2.end());
// Store the remaining characters
string res3;
// Check If any odd character
// appended to the middle of
// the resultant string or not
bool f = false;
// Append all the character which
// occurs odd number of times
for(int i = 0; i < 256; i++) {
// If count of occurrence
// of characters is odd
if(hash[i]%2) {
if(!f) {
res1.push_back(i);
f = true;
}
else {
res3.push_back(i);
}
}
}
return (res1 + res2 + res3);
}
// Driver Code
int main() {
string str = "geeksforgeeks";
cout<<longestPalinSub(str);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to rearrange the string to
// get the longest palindromic substring
static String longestPalinSub(String str)
{
// Stores the length of str
int N = str.length();
// Store the count of occurrence
// of each character
int[] hash = new int[256];
// Traverse the string, str
for(int i = 0; i < N; i++)
{
// Count occurrence of
// each character
hash[str.charAt(i)]++;
}
// Store the left half of the
// longest palindromic substring
StringBuilder res1 = new StringBuilder();
// Store the right half of the
// longest palindromic substring
StringBuilder res2 = new StringBuilder();
// Traverse the array, hash[]
for(int i = 0; i < 256; i++)
{
// Append half of the
// characters to res1
for(int j = 0; j < hash[i] / 2; j++)
{
res1.append((char)i);
}
// Append half of the
// characters to res2
for(int j = (hash[i] + 1) / 2;
j < hash[i]; j++)
{
res2.append((char)i);
}
}
// reverse string res2 to make
// res1 + res2 palindrome
StringBuilder tmp = res2.reverse();
// Store the remaining characters
StringBuilder res3 = new StringBuilder();
// Check If any odd character
// appended to the middle of
// the resultant string or not
boolean f = false;
// Append all the character which
// occurs odd number of times
for(int i = 0; i < 256; i++)
{
// If count of occurrence
// of characters is odd
if (hash[i] % 2 == 1)
{
if (!f)
{
res1.append((char)i);
f = true;
}
else
{
res3.append((char)i);
}
}
}
return (res1.toString() +
tmp.toString() +
res3.toString());
}
// Driver code
public static void main (String[] args)
{
String str = "geeksforgeeks";
System.out.println(longestPalinSub(str));
}
}
// This code is contributed by offbeat
Python3
# Python 3 program to implement # the above approach # Function to rearrange the # string to get the longest # palindromic substring def longestPalinSub(st): # Stores the length of # str N = len(st) # Store the count of # occurrence of each # character hash1 = [0] * 256 # Traverse the string, # str for i in range(N): # Count occurrence of # each character hash1[ord(st[i])] += 1 # Store the left half of the # longest palindromic substring res1 = "" # Store the right half of the # longest palindromic substring res2 = "" # Traverse the array, hash[] for i in range(256): # Append half of the # characters to res1 for j in range(hash1[i] // 2): res1 += chr(i) # Append half of the # characters to res2 for j in range((hash1[i] + 1)//2, hash1[i]): res2 += chr(i) # reverse string res2 to make # res1 + res2 palindrome p = list(res2) p.reverse() res2 = ''.join(p) # Store the remaining characters res3 = "" # Check If any odd character # appended to the middle of # the resultant string or not f = False # Append all the character which # occurs odd number of times for i in range(256): # If count of occurrence # of characters is odd if(hash1[i] % 2): if(not f): res1 += chr(i) f = True else: res3 += chr(i) return (res1 + res2 + res3) # Driver Code if __name__ == "__main__": st = "geeksforgeeks" print(longestPalinSub(st)) # This code is contributed by Chitranayal
C#
// C# program to implement
// the above approach
using System;
using System.Text;
class GFG{
// Reverse string
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 rearrange the string to
// get the longest palindromic substring
static String longestPalinSub(String str)
{
// Stores the length of str
int N = str.Length;
// Store the count of occurrence
// of each character
int[] hash = new int[256];
// Traverse the string, str
for(int i = 0; i < N; i++)
{
// Count occurrence of
// each character
hash[str[i]]++;
}
// Store the left half of the
// longest palindromic substring
StringBuilder res1 = new StringBuilder();
// Store the right half of the
// longest palindromic substring
StringBuilder res2 = new StringBuilder();
// Traverse the array, hash[]
for(int i = 0; i < 256; i++)
{
// Append half of the
// characters to res1
for(int j = 0; j < hash[i] / 2; j++)
{
res1.Append((char)i);
}
// Append half of the
// characters to res2
for(int j = (hash[i] + 1) / 2;
j < hash[i]; j++)
{
res2.Append((char)i);
}
}
// reverse string res2 to make
// res1 + res2 palindrome
String tmp = reverse(res2.ToString());
// Store the remaining characters
StringBuilder res3 = new StringBuilder();
// Check If any odd character
// appended to the middle of
// the resultant string or not
bool f = false;
// Append all the character which
// occurs odd number of times
for(int i = 0; i < 256; i++)
{
// If count of occurrence
// of characters is odd
if (hash[i] % 2 == 1)
{
if (!f)
{
res1.Append((char)i);
f = true;
}
else
{
res3.Append((char)i);
}
}
}
return (res1.ToString() +
tmp.ToString() +
res3.ToString());
}
// Driver code
public static void Main(String[] args)
{
String str = "geeksforgeeks";
Console.WriteLine(longestPalinSub(str));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to rearrange the string to
// get the longest palindromic substring
function longestPalinSub(str)
{
// Stores the length of str
var N = str.length;
// Store the count of occurrence
// of each character
var hash = Array(256).fill(0);
// Traverse the string, str
for(var i = 0; i < N; i++)
{
// Count occurrence of
// each character
hash[str[i].charCodeAt(0)]++;
}
// Store the left half of the
// longest palindromic substring
var res1 = [];
// Store the right half of the
// longest palindromic substring
var res2 = [];
// Traverse the array, hash[]
for(var i = 0; i< 256; i++)
{
// Append half of the
// characters to res1
for(var j = 0; j < parseInt(hash[i] / 2); j++)
{
res1.push(String.fromCharCode(i));
}
// Append half of the
// characters to res2
for(var j = parseInt((hash[i] + 1) / 2);
j < hash[i]; j++)
{
res2.push(String.fromCharCode(i));
}
}
// Reverse string res2 to make
// res1 + res2 palindrome
res2 = res2.reverse();
// Store the remaining characters
var res3 = [];
// Check If any odd character
// appended to the middle of
// the resultant string or not
var f = false;
// Append all the character which
// occurs odd number of times
for(var i = 0; i < 256; i++)
{
// If count of occurrence
// of characters is odd
if (hash[i] % 2)
{
if(!f)
{
res1.push(String.fromCharCode(i));
f = true;
}
else
{
res3.push(String.fromCharCode(i));
}
}
}
return (res1.join('') +
res2.join('') +
res3.join(''));
}
// Driver Code
var str = "geeksforgeeks";
document.write(longestPalinSub(str));
// This code is contributed by noob2000
</script>
Producción
eegksfskgeeor
Complejidad temporal: O(N)
Espacio auxiliar: O(1)