leetcode-409-easy

Longest Palindrome

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.
Example 2:

Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.
Constraints:

1 <= s.length <= 2000
s consists of lowercase and/or uppercase English letters only.

思路一：刚开始没有想到需要加上奇数字符，理解后就简单了，统计字符数，最后统计有多少偶数个数的字符

    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            map.compute(s.charAt(i), (k, v) -> v == null ? 1 : v + 1);
        }

        ArrayList<Integer> values = new ArrayList<>(map.values());
        Collections.sort(values);

        int count = 0;
        boolean addOne = false;
        for (int i = values.size() - 1; i >= 0; i--) {
            int val = values.get(i);
            if (val % 2 == 0) {
                count += val;
            } else {
                count += val - 1;
                addOne = true;
            }
        }

        return addOne ? count + 1 : count;
    }