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>
eegksfskgeeor
Complejidad temporal: O(N)
Espacio auxiliar: O(1)