문자열에서 문자를 제거하거나 섞어서 형성된 가장 긴 회문을 찾습니다.
문자열이 주어지면 문자열에서 문자를 제거하거나 섞어 구성할 수 있는 가장 긴 회문을 찾습니다. 가장 긴 길이의 회문 문자열이 여러 개 있는 경우 하나의 회문만 반환합니다.
예:
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
우리는 회문 문자열을 세 부분으로 나눌 수 있습니다 - 중간과 끝을 구걸하세요. 홀수 길이의 회문 문자열의 경우 2n + 1 'beg'는 문자열의 처음 n 문자로 구성되며 'mid'는 1 문자로만 구성됩니다. 즉 (n + 1)번째 문자와 'end'는 회문 문자열의 마지막 n 문자로 구성됩니다. 길이가 2n인 회문 문자열의 경우 'mid'는 항상 비어 있습니다. 문자열이 회문이 되려면 'end'가 'beg'의 반대가 된다는 점에 유의해야 합니다.
아이디어는 우리 솔루션에서 위의 관찰을 사용하는 것입니다. 문자 섞기가 허용되므로 문자 순서는 입력 문자열에서 중요하지 않습니다. 먼저 입력 문자열에서 각 문자의 빈도를 얻습니다. 그런 다음 입력 문자열에서 짝수(예: 2n)를 갖는 모든 문자는 출력 문자열의 일부가 됩니다. 'beg' 문자열에 n 문자를 쉽게 배치하고 'end' 문자열에 다른 n 문자를 배치할 수 있기 때문입니다(회문 순서를 유지하여). 홀수 문자(예: 2n + 1)가 있는 문자의 경우 'mid'를 해당 문자 중 하나로 채웁니다. 나머지 2n개의 문자는 반으로 나누어 처음과 끝에 추가됩니다.
아래는 위의 아이디어를 구현한 것입니다.
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>
산출
abcdcba
시간 복잡도 위의 솔루션은 O(n)입니다. 여기서 n은 문자열의 길이입니다. 알파벳의 문자 수는 일정하므로 점근 분석에 기여하지 않습니다.
보조 공간 프로그램에서 사용하는 M은 M입니다. 여기서 M은 ASCII 문자 수입니다.
