C++の回文の順列である最大偶数長のサブ文字列

問題の説明

文字列が与えられた場合、タスクは、回文に配置できるサブ文字列の最大長を見つけることです。

例

入力文字列=“ 5432112356”の場合、最大回文サブストリングは“ 321123”であり、その長さは6であるため、回答は6です。

アルゴリズム

• 部分文字列の長さが奇数の場合、最終的な解決策では考慮できません。
• サブ文字列の長さが偶数の場合、そのサブ文字列の各文字が偶数回出現する場合にのみ解決策となる可能性があります。これは、辞書カウントを使用して実行できます。各文字が偶数回出現するかどうかをチェックします。はいの場合、可能な解決策の1つとしてそれを含めます。次に、文字列に次の文字を含めることで次のサブ文字列を形成します。これは、endをインクリメントするだけで実行でき、指定された条件を満たす、可能なすべての最大値を返す、より長いサブ文字列を形成できるかどうかを再帰的にチェックします。ソリューション

例

#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> countt;
bool isPalindromePossible(unordered_map<int, int> &countt) {
   for (auto key : countt) {
      if (key.second & 1) {                                                        
         return false;
      }
      return true;
   }
   int getMaxPalindrome(string str, unordered_map<int, int> &countt, int start, int end) {
      if (end == str.length()) {
         if ((end - start) % 2 == 0)
         if (isPalindromePossible(countt))
         return end - start;
         return 0;
      } else {
      if ((end - start) % 2 == 0) {
         if (isPalindromePossible(countt)) {
            countt[str[end]]++;
            return max(end - start, getMaxPalindrome(str, countt, start, end + 1));
         } else {
            countt[str[end]]++;
            return getMaxPalindrome(str, countt, start, end + 1);
         }
      } else {
         countt[str[end]]++;
         unordered_map<int, int>
         c(countt.begin(), countt.end());
         int length = getMaxPalindrome(str, c, start, end + 1);
         countt[str[end]]--;
         countt[str[start]]--;
         return max(length, getMaxPalindrome(str, countt, start + 1, end));
      }
   }
}
int main(int argc, char const *argv[]) {
   string str = "5432112356";
   int start = 0, end = 0;
   cout << "Maximum palindrome length = " << getMaxPalindrome(str, countt, start, end) << endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Maximum palindrome length = 6