Dada una cadena, encuentre el palíndromo más largo que se pueda construir eliminando o mezclando caracteres de la cadena. Devuelve solo un palíndromo si hay varias cadenas de palíndromos de mayor longitud.
Ejemplos:
Input: abc Output: a OR b OR c Input: aabbcc Output: abccba OR baccab OR cbaabc OR any other palindromic string of length 6. Input: abbaccd Output: abcdcba OR ... Input: aba Output: aba
Podemos dividir cualquier cuerda palindrómica en tres partes: inicio, mitad y final. Para una cadena palindrómica de longitud impar, digamos que 2n + 1 'beg' consta de los primeros n caracteres de la cadena. 'mid' constará de solo 1 carácter, es decir, (n + 1)ésimo carácter y 'end' constará de los últimos n caracteres de la cadena palindrómica. Para una cadena palindrómica de longitud par, 2n 'mid' siempre estará vacía. Cabe señalar que 'fin' será el inverso de 'comienzo' para que la cadena sea palíndromo.
La idea es utilizar la observación anterior en nuestra solución. Como se permite la mezcla de caracteres, el orden de los caracteres no importa en la cadena de entrada. Primero obtenemos la frecuencia de cada carácter en la cadena de entrada. Entonces, todos los caracteres que tengan una aparición par (digamos 2n) en la cadena de entrada serán parte de la cadena de salida, ya que podemos colocar fácilmente n caracteres en la cadena 'inicio' y los otros n caracteres en la cadena 'final' (preservando el orden palindrómico). Para los caracteres que tienen una aparición impar (por ejemplo, 2n + 1), completamos 'mid' con uno de todos esos caracteres. y los 2n caracteres restantes se dividen por la mitad y se agregan al principio y al final.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find the longest palindrome by removing // or shuffling characters from the given string #include
// Java program to find the longest palindrome by removing // or shuffling characters from the given string class GFG { // Function to find the longest palindrome by removing // or shuffling characters from the given string static String findLongestPalindrome(String str) { // to stores freq of characters in a string int count[] = new int[256]; // find freq of characters in the input string for (int i = 0; i < str.length(); i++) { count[str.charAt(i)]++; } // Any palindromic string consists of three parts // beg + mid + end String beg = '' mid = '' end = ''; // solution assumes only lowercase characters are // present in string. We can easily extend this // to consider any set of characters for (char ch = 'a'; ch <= 'z'; ch++) { // if the current character freq is odd if (count[ch] % 2 == 1) { // mid will contain only 1 character. It // will be overridden with next character // with odd freq mid = String.valueOf(ch); // decrement the character freq to make // it even and consider current character // again count[ch--]--; } // if the current character freq is even else { // If count is n(an even number) push // n/2 characters to beg string and rest // n/2 characters will form part of end // string for (int i = 0; i < count[ch] / 2; i++) { beg += ch; } } } // end will be reverse of beg end = beg; end = reverse(end); // return palindrome string return beg + mid + end; } static String reverse(String str) { // convert String to character array // by using toCharArray String ans = ''; char[] try1 = str.toCharArray(); for (int i = try1.length - 1; i >= 0; i--) { ans += try1[i]; } return ans; } // Driver code public static void main(String[] args) { String str = 'abbaccd'; System.out.println(findLongestPalindrome(str)); } } // This code is contributed by PrinciRaj1992
# Python3 program to find the longest palindrome by removing # or shuffling characters from the given string # Function to find the longest palindrome by removing # or shuffling characters from the given string def findLongestPalindrome(strr): # to stores freq of characters in a string count = [0]*256 # find freq of characters in the input string for i in range(len(strr)): count[ord(strr[i])] += 1 # Any palindromic consists of three parts # beg + mid + end beg = '' mid = '' end = '' # solution assumes only lowercase characters are # present in string. We can easily extend this # to consider any set of characters ch = ord('a') while ch <= ord('z'): # if the current character freq is odd if (count[ch] & 1): # mid will contain only 1 character. It # will be overridden with next character # with odd freq mid = ch # decrement the character freq to make # it even and consider current character # again count[ch] -= 1 ch -= 1 # if the current character freq is even else: # If count is n(an even number) push # n/2 characters to beg and rest # n/2 characters will form part of end # string for i in range(count[ch]//2): beg += chr(ch) ch += 1 # end will be reverse of beg end = beg end = end[::-1] # return palindrome string return beg + chr(mid) + end # Driver code strr = 'abbaccd' print(findLongestPalindrome(strr)) # This code is contributed by mohit kumar 29
// C# program to find the longest // palindrome by removing or // shuffling characters from // the given string using System; class GFG { // Function to find the longest // palindrome by removing or // shuffling characters from // the given string static String findLongestPalindrome(String str) { // to stores freq of characters in a string int []count = new int[256]; // find freq of characters // in the input string for (int i = 0; i < str.Length; i++) { count[str[i]]++; } // Any palindromic string consists of // three parts beg + mid + end String beg = '' mid = '' end = ''; // solution assumes only lowercase // characters are present in string. // We can easily extend this to // consider any set of characters for (char ch = 'a'; ch <= 'z'; ch++) { // if the current character freq is odd if (count[ch] % 2 == 1) { // mid will contain only 1 character. // It will be overridden with next // character with odd freq mid = String.Join(''ch); // decrement the character freq to make // it even and consider current // character again count[ch--]--; } // if the current character freq is even else { // If count is n(an even number) push // n/2 characters to beg string and rest // n/2 characters will form part of end // string for (int i = 0; i < count[ch] / 2; i++) { beg += ch; } } } // end will be reverse of beg end = beg; end = reverse(end); // return palindrome string return beg + mid + end; } static String reverse(String str) { // convert String to character array // by using toCharArray String ans = ''; char[] try1 = str.ToCharArray(); for (int i = try1.Length - 1; i >= 0; i--) { ans += try1[i]; } return ans; } // Driver code public static void Main() { String str = 'abbaccd'; Console.WriteLine(findLongestPalindrome(str)); } } // This code is contributed by 29AjayKumar
<script> // Javascript program to find the // longest palindrome by removing // or shuffling characters from // the given string // Function to find the longest // palindrome by removing // or shuffling characters from // the given string function findLongestPalindrome(str) { // to stores freq of characters // in a string let count = new Array(256); for(let i=0;i<256;i++) { count[i]=0; } // find freq of characters in // the input string for (let i = 0; i < str.length; i++) { count[str[i].charCodeAt(0)]++; } // Any palindromic string consists // of three parts // beg + mid + end let beg = '' mid = '' end = ''; // solution assumes only // lowercase characters are // present in string. // We can easily extend this // to consider any set of characters for (let ch = 'a'.charCodeAt(0); ch <= 'z'.charCodeAt(0); ch++) { // if the current character freq is odd if (count[ch] % 2 == 1) { // mid will contain only 1 character. It // will be overridden with next character // with odd freq mid = String.fromCharCode(ch); // decrement the character freq to make // it even and consider current character // again count[ch--]--; } // if the current character freq is even else { // If count is n(an even number) push // n/2 characters to beg string and rest // n/2 characters will form part of end // string for (let i = 0; i < count[ch] / 2; i++) { beg += String.fromCharCode(ch); } } } // end will be reverse of beg end = beg; end = reverse(end); // return palindrome string return beg + mid + end; } function reverse(str) { // convert String to character array // by using toCharArray let ans = ''; let try1 = str.split(''); for (let i = try1.length - 1; i >= 0; i--) { ans += try1[i]; } return ans; } // Driver code let str = 'abbaccd'; document.write(findLongestPalindrome(str)); // This code is contributed by unknown2108 </script>
Producción
abcdcba
Complejidad del tiempo de la solución anterior es O(n) donde n es la longitud de la cadena. Dado que el número de caracteres del alfabeto es constante, no contribuyen al análisis asintótico.
Espacio auxiliar utilizado por el programa es M donde M es el número de caracteres ASCII.