409 Longest Palindrome

409. Longest Palindrome

1. Question

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.

2. Implementation

(1) HashTable

思路: 构建palindrome只能拿出现偶数次数的character加上之多一个奇数次数的character， 用HashSet判断一个字符是否为偶数次出现

class Solution {
    public int longestPalindrome(String s) {
        Set<Character> set = new HashSet<>();
        int count = 0;

        for (char c : s.toCharArray()) {
            if (set.contains(c)) {
                ++count;
                set.remove(c);
            }
            else {
                set.add(c);
            }
        }
        return set.isEmpty()? 2 * count : 2 * count + 1;
    }
}

(2) 空间优化

class Solution {
    public int longestPalindrome(String s) {
        int[] letters = new int[256];

        for (char c : s.toCharArray()) {
            ++letters[c];
        }

        int res = 0;
        boolean hasSingleNumber = false;

        for (int count : letters) {
            if (count % 2 == 0) {
                res += count;
            }
            else {
                if (count > 1) {
                    res += count - 1;
                }
                hasSingleNumber = true;
            }
        }

        if (hasSingleNumber) {
            res += 1;
        }
        return res;
    }
}

3. Time & Space Complexity

HashTable: 时间复杂度O(n), 空间复杂度O(n)

空间优化: 时间复杂度O(n), 空间复杂度O(1)