[leetcode] 409. Longest Palindrome

Description

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.

分析

题目的意思是：可以用该字符串组成的最长回文子串。

• 用hashmap统计字符的频率，然后遍历hash表把词频为偶数加入结果，把词频为奇数-1加入结果，最后我们判断一下是否有奇数，有的化就是res+1，没有的化就是res了。

代码

class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char,int> m;
for(int i=0;i<s.size();i++){
m[s[i]]++;
}
int res=0;
bool mid=false;
for(auto s:m){
if(s.second%2==0){
res+=s.second;
}else if(s.second%2==1){
mid=true;
res+=s.second;
res--;
}
}
return mid ? res+1:res;
}
};

参考文献

[LeetCode] Longest Palindrome 最长回文串