05 August 2008
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.
给一个字符串，里面有大小写，字符可以打乱，问这些字符可以组成的最长的回文结构长度是多少。所以问题就转化为了求偶数个字符的个数，我们了解回文串的都知道，回文串主要有两种形式，一个是左右完全对称的，比如noon，还有一种是以中间字符为中心，左右对称，比如bob，level等，那么我们统计出来所有偶数个字符的出现总和，然后如果有某个字符总数是奇数个字符的话，我们算出偶数的个数，然后最后结果加1即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int pairs = 0;
HashSet<Character> set = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (set.contains(ch)) {
set.remove(ch); //找到成对的字符就删掉
pairs++; // 对子数+1
} else {
set.add(ch);
}
}
if (set.isEmpty()) { // 偶数个对子
return pairs * 2;
}
return pairs * 2 + 1; // 奇数个对子，中间可以放一个字符
}
}
另外hashset.remove(ch)这个方法，如果hashset中有ch这个元素的话可以remove并且返回true，所以可以这样写
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Set<Character> set = new HashSet<>();
int count = 0;
for (char ch : s.toCharArray()) {
if (set.remove(ch)) {//如果hashset中有这个字符，可以remove并返回true
count++;
} else {
set.add(ch);
}
}
return set.size() > 0 ? count*2 + 1 : count*2;
}
}
另外，也可以利用int[26]来检查有多少个相同的字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[] lowercase = new int[26];
int[] uppercase = new int[26];
int result = 0;
for (int i = 0; i < s.length(); i++) {
int ch = s.charAt(i);
if (ch >= 97) {//判断大小写
lowercase[ch - 'a']++;
} else {
uppercase[ch - 'A']++;
}
}
for (int i = 0; i < 26; i++) {//遍历大小写两个数组，看相同的字符有多少
//每两个字符组成一个回文
result += (lowercase[i] / 2) * 2;
result += (uppercase[i] / 2) * 2;
}
return result == s.length() ? result : result + 1;
}
}