题目描述

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

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

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

示例 1:

输入:
“abccccdd”

输出:
7

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

算法1

(Hash) O(n)

回文串有两种形式，一个是偶数个字符左右完全对称的，比如okko, 还有一种是以中间字符为中心，左右对称，比如aba，wow，
那么先统计出来所有偶数个字符的出现的次数，然后如果有奇数个字符的话，我们取取出其最大偶数，然后最后结果加1即可。

Java 代码

public class Solution {

    int[] frequency = new int[128];

    public int longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) {
            return n;
        }

        for (int i = 0; i < n; i++) {
            frequency[s.charAt(i)]++;
        }

        int res = 0;
        boolean flag = false;
        for (int i = 0; i < 128; i++) {
            if (frequency[i] == 0) {
                continue;
            }

            res += frequency[i];
            if (frequency[i] % 2 == 1) {
                res -= 1;
                flag = true;
            }
        }

        return flag ? res + 1 : res;
    }

}