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.
Answer
This is an easy problem, which can be solved using brute force.
Since palindrome is symmetric, there can only be one odd number of letters in a palindrome. Thus, we can find the length of longest palindrome that can be built with those letters through counting how many times of each letter in the given string.
Code
class Solution {
public:
int longestPalindrome(string s) {
int n = s.length();
if(n <= 1) return n;
vector<int> dp(52, 0);
for(char c : s)
{
if(c >= 97) dp[c + 26 - 'a']++;
else dp[c - 'A']++;
}
int odd = 0, even = 0;
for(int i = 0; i < 52; ++i)
{
if(dp[i] != 0)
{
if(dp[i] % 2 == 0) even+=dp[i];
else
{
if(dp[i] == 1) odd++;
else
{
even+=dp[i] - 1;
odd++;
}
}
}
}
return odd > 0 ? even + 1 : even;
}
};
