【LeetCode】Day109-the longest palindrome string

题目

409. 最长回文串【简单】

题解

思路
The palindrome must be symmetric,Since it is mentioned symmetry,This means that each letter needs to appear an even number of times,At most one letter appears an odd number of times,且为1次（贪心思路）

算法
set letterch出现v次,那么我们可以使用ch共$v/2\ast 2$次,There is an odd number of occurrences of any letter,Then it can be used as the center of the palindrome,Center at most only1个.

class Solution {
    
    public int longestPalindrome(String s) {
    
        int n=s.length();
        //统计字符出现次数
        int[] count=new int[128];
        for(int i=0;i<n;i++){
    
            char c=s.charAt(i);
            count[c]++;
        }
        //最长回文串长度
        int res=0;
        for(int i='A';i<='z';i++){
    
            res+=count[i]/2*2;
            //Odd times and no palindrome center
            if(count[i]%2==1&&res%2==0)
                res++;
        }
        return res;
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(S)$,其中 S 为字符集大小