0409. Longest Palindrome (E)

Longest Palindrome (E)

题目

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.

---

题意

用给定的字符集合组成一个最长的回文串。

思路

出现次数为偶数的字符全部可以加入回文串，奇数次的可以-1把偶数部分全部加入，整体只能加一个只出现一次的字符。

---

代码实现

Java

class Solution {
    public int longestPalindrome(String s) {
        int len = 0;
        boolean plusOne = false;
        int[] hash = new int[52];
        for (char c : s.toCharArray()) {
            if (c <= 'Z' && c >= 'A') {
                hash[c - 'A' + 26]++;
            } else {
                hash[c - 'a']++;
            }
        }
        for (int i = 0; i < 52; i++) {
            if (hash[i] > 1 && hash[i] % 2 == 0) {
                len += hash[i];
            } else if (hash[i] > 1) {
                len += hash[i] - 1;
                plusOne = true;
            } else if (hash[i] == 1) {
                plusOne = true;
            }
        }
        return plusOne ? len + 1 : len;
    }
}