leetcode [#409]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example “Aa” is not considered a palindrome here.

Example1:
Input:
“abccccdd”

Output:
7

Explanation:
One longest palindrome that can be built is “dccaccd”, whose length is 7.

---

解决方案

public class Solution {
    public int longestPalindrome(String s) {
        if(s.length() == 0) return 0;
        int res = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < s.length(); i++){
            if(!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i), 1);
            } else {
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
            }
        }
        Iterator it = map.entrySet().iterator();
        boolean oddFlag = false;
        while (it.hasNext()) {
            Map.Entry entry = (Map.Entry) it.next();
            if((Integer)entry.getValue() % 2 == 1) {
                if(!oddFlag) {
                    res += (Integer)entry.getValue();
                    oddFlag = true;
                } else {
                    res += ((Integer)entry.getValue() - 1);
                }
            } else {
                res += (Integer)entry.getValue();
            }
        }
        return res;
    }
}

---

注意事项

1. 遍历字符串，使用hashmap存储，key为字符，value为出现次数。
2. 遍历hashmap进行统计。设置针对奇数个数的字符的标记位，如果当前还未出现过奇数个数的字符，则直接将该个数添加到结果，表明这奇数个字符都可以参与构成回文。否则，表明已经有奇数参与，则当前字符只能取出最大的偶数个（即减1）；对于个数为偶数的字符，直接添加到结果。