题目描述
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
Example1:
输入: "abccccdd" 输出: 7 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
解题思路
- 这里给出了一串字符
- 我们要用给定的字符组成一个回文子串
- 首先我们判断每个字符重复的次数
- 重复了单数次，我们可以 / 2 * 2,即为用偶数的次数
- 然后如果存在单数，我们再累加1次即可
class Solution {
public:
int longestPalindrome(string s) {
// int maxLen = 1;
// int size = s.size();
/*vector<vector<bool>> dp(size, vector<bool>(size, false));
for(int i = 0; i < size; i++){
dp[i][i] = true;
}
for(int i = 0; i < size; i++){
for(int j = 0; j < i; j++){
dp[i][j] = (s[i] == s[j] && (i - j < 2) || (dp[j + 1][i - 1]));
if(dp[i][j] && i - j + 1 > maxLen){
maxLen = i - j + 1;
}
}
}*/
int res = 0;
unordered_map<char, int> mmap;
for(auto& i : s){
mmap[i]++;
}
int flag = 0;
for(auto& p : mmap){
res += p.second / 2 * 2;
if(p.second % 2 == 1 && !flag){ // 单数回文比如说a出现了5次，下边只能增加1次，即其中1个a在中间
flag = 1;
res++;
}
}
return res;
}
};
