题目如下：

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
Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

题目大意

题目的大概意思是，给定一个字符串，要我们找出字符串中可以组合成的最长回文长度，比如abccccdd可以组成的最长回文字符串是dccaccd，长度为7，将其返回即可

思路

一开始想到的思路比较简单，将字符串化成字符数组并排序，遍历此数组，找出所有相同字符的数量，如果为1个，将其忽略，如果是1个以上的奇数，则总长度加上这个奇数减一，如果为1以上的偶数，则总长度直接加和即可。最后仍然需要做一个判定，如果出现这种情况abbccdd，结果应该是7而不是6，需要有一个flag来记录是否出现过单个的字符，因为出现一次的字符可以放在回文的中间，其次，如果出现1以上的奇数，也需要将其记录，如aabbbccdd，结果应该是9而不是8。因为使用了一个字符串数组，因此空间复杂度为O(n)，而只遍历了一次，因此时间复杂度为O(n)。此思路的代码如下：

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
26
27
public int longestPalindrome(String s) {
    char [] cs = s.toCharArray();
    Arrays.sort(cs);
    int result = 0;
    boolean isSingle = false;
    for (int i = 0; i < cs.length; i++) {
        int temp = i;
        while (i + 1 < cs.length && cs[i] == cs[i + 1]) {
            i++;
        }
        if (i != temp) {
            temp = i + 1 - temp;
            if (temp % 2 == 0) {
                result += temp;
            } else {
                result += temp - 1;
                isSingle = true;
            }
        } else {
            isSingle = true;
        }
    }
    if (isSingle) {
        result += 1;
    }
    return result;
}

此代码提交之后通过了，总时长为12ms，超越了74%的提交。

提交结果
提交结果

阅读了一下其他人提交的代码，有的思路是使用HashSet或者HashTable，将字符串拆成数组并排序，遍历此数组，如果在HashSet中发现了该字符，则计数量count加1，否则将此字符加入HashSet，遍历完之后如果发现HashSet不为空，那么最终的长度应该是count的两倍加1，否则最终的长度为count的两倍。此思路空间复杂度为O(n)，时间复杂度也为O(n)。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int longestPalindrome_v2(String s) {
    if(s==null || s.length()==0) return 0;
    HashSet<Character> hs = new HashSet<Character>();
    int count = 0;
    for(int i=0; i<s.length(); i++){
        if(hs.contains(s.charAt(i))){
            hs.remove(s.charAt(i));
            count++;
        }else{
            hs.add(s.charAt(i));
        }
    }
    if(!hs.isEmpty()) return count*2+1;
    return count*2;
}

提交结果：

提交结果
提交结果