leetcode 409：給定字符串，求能重組成的最長(zhǎng)回文字符串

# -*- 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:
    """
    給定一個(gè)字符串，問其中的字符最多能組成多長(zhǎng)的回文字符串？

    其實(shí)我們可以這樣想，所謂的回文字符串，就是從左到右和從右到左的遍歷是一樣的，那么就是說(shuō)，
    每個(gè)字符都需要出現(xiàn)偶數(shù)次，當(dāng)然，如果是奇數(shù)長(zhǎng)度的回文字符串，其中間的字符可以是只出現(xiàn)了一次。

    也就是說(shuō)，我們只需要判斷給定的字符串中各個(gè)字符的出現(xiàn)次數(shù)，把偶數(shù)次的字符挑出來(lái)，然后從奇數(shù)次的
    字符中找一個(gè)(如果存在出現(xiàn)次數(shù)為奇數(shù)的字符的話)，這些字符就能組成最長(zhǎng)的回文字符串。
    """
    def longestPalindrome(self, s: str) -> int:
        from collections import Counter
        # 找出所有奇數(shù)次的字符
        odds = sum(v & 1 for v in Counter(s).values())
        # 先把奇數(shù)次的字符去掉，然后從中找一個(gè)(如果有)
        return len(s) - odds + bool(odds)