409. 最长回文串

题意：给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

解题思路

解法1：
1.分析题意，字符串并未要求顺序固定，也就是说，我们可以重组字符串
2.回文字符串的特征是，双数的字符肯定可以构成回文字符串，单数的只能有一个
3.用hashmap保存数据，key为每个字符，value为出现的次数
4.遍历map，如果出现是偶数次的字符，必定可以成为回文字符串的一部分；如果出现是奇数次的字符，则n-1个此字符必定可以成为回文字符串的一部分，过程中，需要注意，奇数出现之后，结果需要+1
此解法，时间复杂度是O（n）,空间复杂度是O（n）
运行效率为：

运行效率.png

解题遇到的问题

无

后续需要总结学习的知识点

无

##解法1
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;

class Solution {
    public int longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s.length();
        }

        // 回文字符串的特征是，双数的字符肯定可以构成回文字符串，单数的只能有一个
        // 用hashmap保存数据，key为每个字符，value为出现的次数]
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }

        Iterator<Entry<Character, Integer>> iterator = map.entrySet()
                .iterator();
        int ans = 0;
        // 标记过程中，是否有单个的字符出现
        boolean flag = false;
        while (iterator.hasNext()) {
            Entry<Character, Integer> entry = iterator.next();
            if (entry.getValue() % 2 == 0) {
                // 如果出现是偶数次的字符，必定可以成为回文字符串的一部分
                ans += entry.getValue();
            } else {
                // 如果出现是奇数次的字符，则n-1个此字符必定可以成为回文字符串的一部分
                ans += entry.getValue() - 1;
                flag = true;
            }

        }
        return flag ? ++ans : ans;
    }

}