【LeetCode】Day109-最长回文串

题目

409. 最长回文串【简单】

题解

思路
回文串必须是对称的，那既然提到对称，就说明每个字母都需要出现偶数次，至多只有一个字母出现奇数次，且为1次（贪心思路）

算法
设字母ch出现v次，那么我们可以使用ch共$v/2\ast 2$次，有任何一个字母出现奇数次，则可以把它作为回文串中心，中心最多仅有1个。

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;
            //奇数次且没有回文中心
            if(count[i]%2==1&&res%2==0)
                res++;
        }
        return res;
    }
}

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

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