已知一个只包括大小写字符的字符串，求用该字符串中的字符可以生 成的最长回文字符串长度。
例如 s = “abccccddaa”，可生成的最长回文字符串长度为9，如dccaaaccd、 adccbccda、 acdcacdca等，都是正确的。
LeetCode 409. Longest Palindrome
思考
例如在s = “abccccddaa”中，有3个a，1个b，4个c，2个d。 使用字符串s中的字符，任意组合，生成新的字符串，若生成的字符串为 回文字符串，需要除了中心字符，其余字符只要头部出现，尾部 就要对应出现。
例如: a...a、ccd...dcc、cc...d...cc
分析
例如，在s = “abccccddaa”中，有3个a，1个b，4个c，2个d。
1.在字符串中，字符数量为偶数的字符: 全部使用，头部放一个字符，尾部就对应放一个。 如，4个c和2个d可全部用上:...ccd...dcc...、...cdc...cdc...、...dcc...ccd...等。
2.在字符串中，字符数量为奇数的字符:丢掉一个字符，剩下的字符数为偶数个，按照字符数量为偶数的字符处理。 如，3个a中，有2个a可以用上:...a...a...
3.若有剩余的字符，如: 1个a、1个b
随便选择1个字符当作中心字符:...a...、...b...
算法设计
1.利用字符哈希方法，统计字符串中所有的字符数量;
2.设置最长回文串偶数字符长度为max_length = 0;
3.设置是否是否有中心点标记 flag = 0;
4.遍历每一个字符，字符数为count，若count为偶数，max_length += count;若count 为奇数，max_length += count – 1，flag = 1;
5.最终最长回文子串长度: max_length + flag。
class Solution{
public:
int longestPalindrome(std::string s){
int char_map[128]={0};字符哈希
int max_length = 0;//回文串偶数部分最大长度
int flag = 0;//是否有中心点
for(int i = 0; i < s.length; i++){
char_map[s[i]]++;
}
for(int i = 0; i < 128; i++){
if(char_map[i] % 2 == 0){
max_length += char_map[i];
}
else{
max_length += char_map[i] - 1;
flag = 1;
}
}
return max_length +flag;
}
};
测试
int main(){
std::string s= "abcdcccddaa";
Solution solve;
printf("%d\n",solve.longestPalindrome(s));
return 0;
}
