Longest Palindrome

Problem

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.

Solution

public class Solution {
    public int longestPalindrome (String s) {
        if (s == null || s.length() == 0) return 0;
        int[] letters = new int[52];
        for (char ch : s.toCharArray()) {
            if (Character.isLowerCase(ch)) letters[ch - 'a']++;
            else letters[Character.toLowerCase(ch) - 'a' + 26]++;
        }
        int res = 0;
        for (int count : letters) res += count / 2 * 2;
        return res == s.length() ? res : res + 1;
    }
}

Analysis

Because there are upper case and lower case letters, we have to create an array with length 52
Character A is smaller than a when it comes to numeric value and not continuous
Therefore, we use helper method in Character class
After that, we just count how many pairs in letters
Notice that we need to compare res with s.length()
Ex: aaa returns 3 but aa returns 2

Complexity:

• Time: O(n), liner time used
• Space: O(1), only constant space used