Finn lengste palindrom dannet ved å fjerne eller blande tegn fra streng
Gitt en streng, finn det lengste palindromet som kan konstrueres ved å fjerne eller blande tegn fra strengen. Returner bare ett palindrom hvis det er flere palindromstrenger med lengst lengde.
Eksempler:
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
Vi kan dele hvilken som helst palindromisk streng i tre deler - beg i midten og slutten. For palindromiske strenger med odde lengde, si at 2n + 1 'beg' består av de første n tegnene i strengen 'midt' vil bestå av bare 1 tegn, dvs. (n + 1) tegn og 'slutt' vil bestå av de siste n tegnene i den palindromiske strengen. For palindromisk streng med jevn lengde vil 2n 'midt' alltid være tom. Det skal bemerkes at 'slutt' vil være motsatt av 'beg' for at strengen skal være palindrom.
Tanken er å bruke ovenstående observasjon i løsningen vår. Siden stokking av tegn er tillatt, betyr ikke rekkefølgen av tegn noen rolle i inndatastrengen. Vi får først frekvensen til hvert tegn i inndatastrengen. Da vil alle tegn som har jevn forekomst (si 2n) i inndatastrengen være en del av utdatastrengen, da vi enkelt kan plassere n tegn i 'beg'-strengen og de andre n tegnene i 'end'-strengen (ved å bevare den palindromiske rekkefølgen). For tegn som har odd forekomst (si 2n + 1) fyller vi 'midt' med ett av alle slike tegn. og resterende 2n tegn deles i to og legges til på begynnelsen og slutten.
Nedenfor er implementeringen av ideen ovenfor
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>
Produksjon
abcdcba
Tidskompleksitet av løsningen ovenfor er O(n) hvor n er lengden på strengen. Siden antall tegn i alfabetet er konstant, bidrar de ikke til asymptotisk analyse.
Hjelpeplass brukt av programmet er M hvor M er antall ASCII-tegn.
