За даним рядком знайдіть найдовший паліндром, який можна побудувати шляхом видалення або перемішування символів із рядка. Повертає лише один паліндром, якщо є кілька рядків паліндрому найбільшої довжини.
приклади:
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 «початок» складається з перших n символів рядка, «середина» складатиметься лише з 1 символу, тобто (n + 1)-й символ, а «кінець» складатиметься з останніх n символів паліндромного рядка. Для паліндромного рядка парної довжини 2n 'mid' завжди буде порожнім. Слід зазначити, що «end» буде зворотним до «beg», щоб рядок був паліндромом.
виділений html
Ідея полягає в тому, щоб використати вищевказане спостереження в нашому рішенні. Оскільки допускається перемішування символів, порядок символів не має значення у вхідному рядку. Спочатку ми отримуємо частоту кожного символу у вхідному рядку. Тоді всі парні символи (скажімо, 2n) у вхідному рядку будуть частиною вихідного рядка, оскільки ми можемо легко розмістити n символів у рядку «початок», а інші n символів — у рядку «кінець» (зберігаючи паліндромний порядок). Для символів, які зустрічаються непарно (скажімо, 2n + 1), ми заповнюємо «середину» одним із усіх таких символів. а решта 2n символів поділено навпіл і додано на початку та в кінці.
int до рядка c++
Нижче представлена реалізація вищезазначеної ідеї
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>
Вихід
abcdcba
Часова складність наведеного вище рішення дорівнює O(n), де n – довжина рядка. Оскільки кількість символів в алфавіті постійна, вони не сприяють асимптотичному аналізу.
Допоміжне приміщення Програма використовує M, де M — кількість символів ASCII.