题目、409. 最长回文串

原题链接：409. 最长回文串

题目描述：

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

在构造过程中，请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。
/
示例 1:
输入:s = “abccccdd”
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
/
示例 2:
输入:s = “a”
输入:1

解题思路：
对于字符串出现的每个字符，我们可以使用该字符 v / 2 * 2 次，回文串平分两半，每半分得 v / 2 个字符 ，其中 / 为整数除法。如：9 / 2 = 4；1 / 2 = 0（v为字符出现的次数）

如果有任何一个字符出现奇数次，我们选出现的第一个字符，取其一个单字符作为唯一的回文中心，因为最多只能有一个字符作为回文中心。

为了做到出现的首个奇数次元素作为唯一回文中心，我们需要满足条件：回文长度为偶数，且字符出现奇数次；
满足条件，回文长度加一，回文长度就变成奇数，保证只有一个或没有回文中心。

我用了HashMap集合来记录字符出现的次数，再用迭代器遍历。（用时和内存都比较多）

代码：

class Solution {
    public int longestPalindrome(String s) {
        char[] arr = s.toCharArray();//字符串转为数组，每个元素都是字符串中的一个字符
        Map<Character,Integer> map = new HashMap<>();//创建双列集合map
        for(char c :arr ){//增强for循环，遍历数组
            if(map.containsKey(c)){//如果字符存在，出现次数value值+1
                map.replace(c,map.get(c).intValue()+1);
            }else{//如果字符不在集合中，创建集合，主键为字符，value值为出现次数1
                map.put(c,1);
            }
        }

        int len = 0;//表示回文串长度
        //实用迭代器Iterator遍历集合元素
        Iterator<Map.Entry<Character,Integer>> iterator = map.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry<Character,Integer> entry = iterator.next();
            len += entry.getValue()/2*2;//可以使用该字符 v / 2 * 2 次
            if(len%2==0 && entry.getValue()%2 ==1)//第一个出现的奇数次的元素作为回文串唯一中心
            len++;
        }
        return len;
    }
}

提交结果：

。。。

思路相同，用数组遍历：
（将字符作为数组下标，数组识别的下标为字符的ASCII码值）

代码（快贼多）：

class Solution {
    public int longestPalindrome(String s) {
        int[] count = new int[128];
        int length = s.length();
        for (int i = 0; i < length; ++i) {
            char c = s.charAt(i);
            count[c]++;
        }

        int ans = 0;
        for (int v: count) {
            ans += v / 2 * 2;
            if (v % 2 == 1 && ans % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }
}

提交结果：