本文共 1911 字，大约阅读时间需要 6 分钟。

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.

Note:

Example:

Input:

“abccccdd”

Output:

7

Explanation:

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

我的想法

遍历字符串，对字符频率进行统计，所有的偶数都可以直接count。奇数次字符需要注意（这个bug找了好久！）：每个字符不是一个整体，假设a出现了5次，我可以只count 4！。这意味着所有的奇数次字符在count的时候需要-1。而在函数返回时需要注意（这里第一次也写错了！！）：如果有>=3的奇数次字符需要在最后返回时+1，以构成奇数型回文串...aba...。如果没有，比如...aa...，不要+1！！！！

class Solution {
       public int longestPalindrome(String s) {
           if(s == null || s.length() == 0) return 0;        Map
   
     map = new HashMap<>();        int res = 0;        for(int i = 0; i < s.length(); i++) {
               Integer count = map.get(s.charAt(i));            if(count != null) {
                   map.put(s.charAt(i), ++count);            }            else {
                   map.put(s.charAt(i), 1);            }        }        ArrayList
    
      list = new ArrayList<>(map.values());        boolean oddCenter = false;        for(int i = 0; i < list.size(); i++){
               int count = list.get(i);            if(count % 2 == 1) oddCenter = true;            res += (count % 2 == 0) ? count : count - 1;        }        return oddCenter ? res + 1 : res;    }}
    
   

解答

leetcode solution: Greedy

class Solution {
       public int longestPalindrome(String s) {
           int[] count = new int[128];        for (char c: s.toCharArray())            count[c]++;        int ans = 0;        for (int v: count) {
               ans += v / 2 * 2;            //判断是否有unique center            if (ans % 2 == 0 && v % 2 == 1)                ans++;        }        return ans;    }}

转载地址：http://nkqvb.baihongyu.com/