Star

Leetcode 409. Longest Palindrome

Posted on | In |

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:

1
2
3
4
5
6
7
8
Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

Explanation:

超简单的题。 Solution 1: 可以用数组存储每个字母的次数，但是需要考虑大小写字母，分开根据ascii计算index。 Solution 2: 用Hashmap存储每个字符出现的次数，加和所有even次数，再加和odd/2*2，如果出现过odd，最后加上1，否则不加。 Solution 3:
用HashSet，如果出现过，就加2，去掉。再出现，再加入。最后如果set是空的，说明没有odd，否则加上1。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
public int longestPalindrome(String s) {
    HashSet<Character> set = new HashSet<>();
    int count = 0;
    for (Character c: s.toCharArray()) {
        if (set.contains(c)) {
            count += 2;
            set.remove(c);
        } else set.add(c);
    }
    if (!set.isEmpty()) count++;
    return count;
}