409.最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

注意:
假设字符串的长度不会超过 1010。

示例 1:

1
2
3
4
5
6
7
8
输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

Solution

这道题当然可以先统计字符出现次数，偶数对的次数×2+1或者就是偶数对的次数×2，不过排序也可以，虽然时间复杂度差了一点

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
class Solution {
    public int longestPalindrome(String s) {
            if(s.length()<2){
                return s.length();
            }
           
            char [] c=s.toCharArray();
            Arrays.sort(c);
           
            int i=0;
            int count=0;
            
            while(i<c.length-1){
                if(c[i]==c[i+1]){
                    count++;
                    i+=2;
                }else{
                i++;
                }
                
            }
            if(count*2==s.length()){
                return count*2;
            }
            return  count*2+1;
    }
}