409. Longest Palindrome - jiejackyzhang/leetcode-note GitHub Wiki

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.

解题思路为：

若一个字符出现的次数为偶数次，则它全部可以在回文字符串中；若出现的次数为奇数次，则需要剩余一个； 在所有奇数次数的字符中，可以选择一个放在中间。

因此这里采用一个int数组来记录字符出现的奇偶，最后将string中所有奇数次数的字符减掉一个，最后在加上1（如果存在奇数次数的字符）即可。

public class Solution {
    public int longestPalindrome(String s) {
        int[] count = new int[58];
        for(char c : s.toCharArray()) {
            if(count[c-'A'] > 0) count[c-'A']--;
            else count[c-'A']++;
        }
        int counter = 0;
        for(int i : count) {
            if(i > 0) counter++;
        }
        return s.length() - counter + ((counter > 0) ? 1 : 0);
    }
}