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)