leetcode 409：给定字符串，求能重组成的最长回文字符串

# -*- coding: utf-8 -*-
# @Time         : 2019-10-11 10:56
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : longestPalindrome.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

"""
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.
"""

class Solution:
    """
    给定一个字符串，问其中的字符最多能组成多长的回文字符串？

    其实我们可以这样想，所谓的回文字符串，就是从左到右和从右到左的遍历是一样的，那么就是说，
    每个字符都需要出现偶数次，当然，如果是奇数长度的回文字符串，其中间的字符可以是只出现了一次。

    也就是说，我们只需要判断给定的字符串中各个字符的出现次数，把偶数次的字符挑出来，然后从奇数次的
    字符中找一个(如果存在出现次数为奇数的字符的话)，这些字符就能组成最长的回文字符串。
    """
    def longestPalindrome(self, s: str) -> int:
        from collections import Counter
        # 找出所有奇数次的字符
        odds = sum(v & 1 for v in Counter(s).values())
        # 先把奇数次的字符去掉，然后从中找一个(如果有)
        return len(s) - odds + bool(odds)