Znajdź najdłuższy palindrom utworzony przez usunięcie lub przetasowanie znaków z łańcucha
Biorąc pod uwagę ciąg znaków, znajdź najdłuższy palindrom, jaki można skonstruować, usuwając lub przetasowując znaki z ciągu. Zwraca tylko jeden palindrom, jeśli istnieje wiele ciągów palindromów o najdłuższej długości.
Przykłady:
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
Możemy podzielić dowolny ciąg palindromiczny na trzy części – zaczynając od środka i na końcu. W przypadku ciągu palindromicznego o nieparzystej długości powiedzmy, że 2n + 1 „beg” składa się z pierwszych n znaków ciągu „mid” będzie składać się tylko z 1 znaku, tj. (n + 1) tego znaku, a „end” będzie składać się z n ostatnich znaków ciągu palindromicznego. Dla łańcucha palindromowego o parzystej długości 2n 'mid' będzie zawsze puste. Należy zauważyć, że „koniec” będzie odwrotnością „błagania”, aby ciąg znaków był palindromem.
Pomysł jest taki, aby w naszym rozwiązaniu wykorzystać powyższą obserwację. Ponieważ dozwolone jest tasowanie znaków, kolejność znaków w ciągu wejściowym nie ma znaczenia. Najpierw uzyskujemy częstotliwość każdego znaku w ciągu wejściowym. Wtedy wszystkie znaki występujące parzyście (powiedzmy 2n) w ciągu wejściowym będą częścią ciągu wyjściowego, ponieważ możemy łatwo umieścić n znaków w ciągu „beg”, a pozostałych n znaków w ciągu „end” (zachowując porządek palindromiczny). W przypadku znaków mających dziwne występowanie (powiedzmy 2n + 1) wypełniamy „środek” jednym ze wszystkich takich znaków. a pozostałe 2n znaków są dzielone na połowy i dodawane na początku i na końcu.
Poniżej realizacja powyższego pomysłu
C++ // C++ program to find the longest palindrome by removing // or shuffling characters from the given string #include using namespace std ; // Function to find the longest palindrome by removing // or shuffling characters from the given string string findLongestPalindrome ( string str ) { // to stores freq of characters in a string int count [ 256 ] = { 0 }; // find freq of characters in the input string for ( int i = 0 ; i < str . size (); 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 ] & 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 -- ] -- ; } // 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 . push_back ( ch ); } } // end will be reverse of beg end = beg ; reverse ( end . begin () end . end ()); // return palindrome string return beg + mid + end ; } // Driver code int main () { string str = 'abbaccd' ; cout < < findLongestPalindrome ( str ); return 0 ; }
Java // 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 # 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# // 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
JavaScript < 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>
Wyjście
abcdcba
Złożoność czasowa powyższego rozwiązania to O(n), gdzie n jest długością struny. Ponieważ liczba znaków w alfabecie jest stała, nie mają one wpływu na analizę asymptotyczną.
Przestrzeń pomocnicza używana przez program to M, gdzie M to liczba znaków ASCII.
