Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example "Aa" is not considered a palindrome here.
Note:
Assume the length of given string will not exceed 1,010.
Example:
Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
給定只含有小寫字母或大寫字母的字符串，找出這些字母能組合而成的最長回文字符串的長度。
這里認(rèn)為大小寫敏感烁峭，即A和a是兩個(gè)不同的字符娇昙。
注：可認(rèn)為給定的字符串長度不超過1010.
思路
統(tǒng)計(jì)每個(gè)字母出現(xiàn)的頻次洁墙，再掃描頻次加入結(jié)果癌别，偶數(shù)個(gè)字符的由于可全部加入回文組合歼争，可直接計(jì)入最后結(jié)果响迂，奇數(shù)個(gè)字符的由于大于1的可加入考抄，如果有多個(gè)一個(gè)字符的則只能取其一，需設(shè)置標(biāo)志蔗彤，再將所有奇數(shù)字符數(shù)減1計(jì)入最后結(jié)果川梅，再根據(jù)標(biāo)志位選擇最后結(jié)果是否補(bǔ)加1.
class Solution {
public:
int longestPalindrome(string s) {
vector<int> letterCount(52,0);
for(auto it=s.begin();it!=s.end();it++){
int letter=0;
if(*it<='Z'&&*it>='A') letter=*it-'A';
else letter=*it-'a'+26;
letterCount[letter]++;
}
bool hasSingle=false;
int res=0;
for(auto it=letterCount.end()-1;it>=letterCount.begin();it--){
if(*it%2==1){
hasSingle=true;
res+=(*it)-1;
}
else res+=(*it);
}
return hasSingle?res+1:res;
}
};
