题目描述

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:

Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

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

解法一

思路

这题是说从原字符串中挑选若干字符,重新组合使其形成最长的回文字符串。那么不妨来看看回文字符串的特点,以dccaccd为例,其中d出现了2次、c出现了4次、a出现了1次,也就是说,回文字符串除了最中间的字符可以仅出现1次外,其他的字符都需要出现2的倍数次。

那么反推就可以知道,只需要统计原字符串中每个字符出现的次数,然后将其全部向下取偶数(即4->45->4)再求和,以及如果存在出现奇数次的字符,则在和的基础上再加1,就是最终结果了。

“统计原字符串中每个字符出现的次数”一般是用Map来保存,而考虑到题目中字符串中字符只可能是小写或大写字母,所以我们可以直接用数组来模拟Map。

Python

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        count_array = [0] * (ord('z') - ord('A') + 1)
        pair = 0
        is_odd_exists = False
        for item in s:
            count_array[ord(item) - ord('A')] += 1
        for item in count_array:
            pair += item // 2
            if not is_odd_exists:
                is_odd_exists = item % 2 != 0
        return pair * 2 + (1 if is_odd_exists else 0)

Java

public class Solution {
    public int longestPalindrome(String s) {
        int[] countArray = new int['z' - 'A' + 1];
        int pair = 0;
        boolean isOddExists = false;
        for (char item : s.toCharArray()) {
            countArray[item - 'A']++;
        }
        for (int item : countArray) {
            pair += item / 2;
            if (!isOddExists) {
                isOddExists = item % 2 != 0;
            }
        }
        return pair * 2 + (isOddExists ? 1 : 0);
    }
}

C++

class Solution {
public:
    int longestPalindrome(string s) {
        int countArray['z' - 'A' + 1] = {0};
        int pair = 0;
        bool isOddExists = false;
        for (char item : s) {
            countArray[item - 'A']++;
        }
        for (int item : countArray) {
            pair += item / 2;
            if (!isOddExists) {
                isOddExists = item % 2 == 1;
            }
        }
        return pair * 2 + (isOddExists ? 1 : 0);
    }
};