数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中最大偶长回文排列子串
问题陈述
给定一个字符串，任务是找到可以排列成回文的最长子串。
示例
如果输入字符串 = “5432112356”，则答案为 6，因为最长的回文子串是 “321123”，其长度为 6
算法
- 如果子串的长度是奇数，则它不能被考虑在最终解中。
- 如果子串的长度是偶数，则只有当子串中每个字符出现的次数都是偶数时，它才可能是解，这可以使用字典计数来完成。我们检查每个字符是否出现偶数次。如果是，则将其包含为可能的解之一。然后，我们通过在字符串中包含下一个字符来形成下一个子串，这可以通过简单地递增结束位置来完成，并递归检查是否可以形成满足给定条件且长度更大的子串，并返回所有可能解的最大值。
示例
#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
更新于：2020年1月10日
109 次浏览
广告