409-最长回文串

LeetCode 409. Longest Palindrome

LeetCode-409

Given a string str which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, “Aa” is not considered a palindrome here.

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

method

题意：统计用所给字符能组成的最长回文串，区分大小写

统计每个字母出现的次数，因为区分大小写，所以直接用256长度的数组

aaabbbc对应有3个a，3个b，1个c，所以先取2个a，2个b，组成回文ab_ba，中间可以再填一个，a或b或c，如果是奇数的话会因为取整而减少，最后再加1个放中间

int longestPalindrome(string str) {
    int nums[256] = {0};    // 一定要给个数，不然会随机初始化
    for (auto s : str) nums[int(s)]++;
    int sum = 0;
    for (auto n : nums)
        sum += (n / 2) * 2;
    return sum < str.size() ? sum + 1 : sum;
}