Nájdite najdlhší palindróm vytvorený odstránením alebo premiešaním znakov z reťazca
Zadaný reťazec nájdite najdlhší palindróm, ktorý možno vytvoriť odstránením alebo premiešaním znakov z reťazca. Vráťte iba jeden palindróm, ak existuje viacero palindrómových reťazcov s najdlhšou dĺžkou.
Príklady:
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
Ľubovoľnú palindromickú strunu môžeme rozdeliť na tri časti – beg mid a end. Pre palindromický reťazec nepárnej dĺžky povedzme, že 2n + 1 „beg“ pozostáva z prvých n znakov reťazca „mid“ bude pozostávať iba z 1 znaku, t. j. (n + 1)-tý znak a „end“ bude pozostávať z posledných n znakov palindromického reťazca. Pre palindromickú strunu párnej dĺžky bude 2n 'mid' vždy prázdne. Treba poznamenať, že 'end' bude opakom 'beg', aby reťazec bol palindróm.
Cieľom je použiť vyššie uvedené pozorovanie v našom riešení. Keďže je povolené miešanie znakov, na poradí znakov vo vstupnom reťazci nezáleží. Najprv získame frekvenciu každého znaku vo vstupnom reťazci. Potom všetky znaky s párnym výskytom (povedzme 2n) vo vstupnom reťazci budú súčasťou výstupného reťazca, pretože môžeme jednoducho umiestniť n znakov do reťazca „beg“ a ďalších n znakov do reťazca „end“ (pri zachovaní palindromického poradia). Pre znaky s nepárnym výskytom (povedzme 2n + 1) vyplníme 'mid' jedným zo všetkých takýchto znakov. a zvyšných 2n znakov sú rozdelené na polovice a pridané na začiatok a koniec.
Nižšie je uvedená implementácia vyššie uvedenej myšlienky
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>
Výstup
abcdcba
Časová zložitosť vyššie uvedeného riešenia je O(n), kde n je dĺžka reťazca. Keďže počet znakov v abecede je konštantný, neprispievajú k asymptotickej analýze.
Pomocný priestor používaný programom je M, kde M je počet znakov ASCII.
