C ++中回文排列的最大偶数长度子字符串

问题陈述

给定一个字符串，任务是找到可以排列成回文式的子字符串的最大长度。

示例

如果输入字符串=“ 5432112356”，则答案为6，因为最大回文子字符串为“ 321123”，其长度为6

算法

• 如果子字符串的长度为奇数，则无法在最终解决方案中考虑它。

• 如果子字符串的长度是偶数，则只有当该子字符串中的每个字符出现偶数次（使用字典计数可以完成）时，它才可能是可行的解决方案。我们检查每个字符是否出现偶数次。如果是，那么我们将其作为可能的解决方案之一。然后，我们通过在字符串中包含下一个字符来形成下一个子字符串，这可以通过简单地增加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