# 409 Longest Palindrome

## 409. [Longest Palindrome](https://leetcode.com/problems/longest-palindrome/description/)

## 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) 空间优化**

```java
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)