C++で文字列から文字を削除またはシャッフルすることによって形成された最長の回文を検索します

コンセプト

与えられた文字列に関して、文字列から文字を削除またはシャッフルすることによって形成できる最長の回文を決定します。最長の長さの回文ストリングが複数あることが観察された場合は、最後に1つの回文のみを返します。

入力

pqr

出力

p OR q OR r

入力

ppqqrr

出力

pqrrqp OR qprrpq OR rqppqr OR
any other palindromic string of length 6.

入力

pqp

出力

pqp

メソッド

ここでは、回文文字列を3つの部分（頼む、中間、終了）に分割できます。奇数の長さの回文文字列、たとえば2n + 1に関して、ここで「beg」は文字列の最初のn文字で構成され、「mid」は（n + 1）番目の文字を意味する1文字のみで構成され、「end」は最後のn文字で構成されます。回文文字列。長さ2nのパリンドロームストリングに関しては、「中央」では常に空になります。文字列が回文になる順序に関して、「終了」が「頼む」の逆になることはすでにわかっています。現在の概念は、上記の観察結果をソリューションに実装することです。文字のシャッフルが許可されているため、入力文字列内の文字の順序は関係ありません。ここで、最初に入力文字列の各文字の頻度を取得します。その後、入力文字列に偶数（たとえば2n）が含まれるすべての文字が出力文字列の一部になります。これは、「beg」文字列にn文字、「end」文字列に他のn文字を簡単に設定できるためです（保存することで）。回文順序）。奇数の文字（たとえば2n + 1）については、ここでは「mid」にそのような文字の1つを入力し、残りの2n文字を半分に分割して、開始時と終了時に追加します。

例

// C++ program to find the longest palindrome by removing
// or shuffling characters from the given string
#include <bits/stdc++.h>
using namespace std;
// Shows function to find the longest palindrome by removing
// or shuffling characters from the given string
string findLongestPalindrome(string str1){
   // Indicated to stores freq of characters in a string
   int count1[256] = { 0 };
   // Determine freq of characters in the input string
   for (int i = 0; i < str1.size(); i++)
      count1[str1[i]]++;
   // Shows any palindromic string consisting of three parts
   // beg1 + mid1 + end1
   string beg1 = "", mid1 = "", end1 = "";
   //Here solution assumes only lowercase characters are
   // present in string. We can easily extend this
   // to consider any set of characters
   for (char ch1 = 'a'; ch1 <= 'z'; ch1++){
      // Now if the current character freq is odd
   if (count1[ch1] & 1){
      // Here mid1 will contain only 1 character. It
      // will be overridden with next character
      // with odd freq
      mid1 = ch1;
      // Here decrement the character freq to make
      // it even and consider current character
      // again
      count1[ch1--]--;
   }
   // Here if the current character freq is even
   else{
      // Now 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 < count1[ch1]/2 ; i++)
         beg1.push_back(ch1);
      }
   }
   // Here end will be reverse of beg
   end1 = beg1;
   reverse(end1.begin(), end1.end());
   // Now return palindrome string
   return beg1 + mid1 + end1;
}
// Driver code
int main(){
   string str1 = "pqqprrs";
   cout << findLongestPalindrome(str1);
   return 0;
}

出力

pqrsrqp