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