Google
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:
1
Input: "abccccdd"
2
3
Output: 7
4
5
Explanation:
6
One longest palindrome that can be built is "dccaccd", whose length is 7.
Copied!

2. Implementation

(1) HashTable
思路: 构建palindrome只能拿出现偶数次数的character加上之多一个奇数次数的character, 用HashSet判断一个字符是否为偶数次出现
1
class Solution {
2
public int longestPalindrome(String s) {
3
Set<Character> set = new HashSet<>();
4
int count = 0;
5
6
for (char c : s.toCharArray()) {
7
if (set.contains(c)) {
8
++count;
9
set.remove(c);
10
}
11
else {
12
set.add(c);
13
}
14
}
15
return set.isEmpty()? 2 * count : 2 * count + 1;
16
}
17
}
Copied!
(2) 空间优化
1
class Solution {
2
public int longestPalindrome(String s) {
3
int[] letters = new int[256];
4
5
for (char c : s.toCharArray()) {
6
++letters[c];
7
}
8
9
int res = 0;
10
boolean hasSingleNumber = false;
11
12
for (int count : letters) {
13
if (count % 2 == 0) {
14
res += count;
15
}
16
else {
17
if (count > 1) {
18
res += count - 1;
19
}
20
hasSingleNumber = true;
21
}
22
}
23
24
if (hasSingleNumber) {
25
res += 1;
26
}
27
return res;
28
}
29
}
Copied!

3. Time & Space Complexity

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