0409._Longest_Palindrome.md

409. Longest Palindrome

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/longest-palindrome/

内容描述

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.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

代码自带解题思路, beats 37.45%

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        lookup = collections.Counter(s)
        res, one = 0, False # one 代表是否存在一个char，其出现次数为奇数
        for k, v in lookup.items():
            if v % 2 == 0:
                res += v # 出现次数为偶数的char可以全部拿走
            else:
                res += v - 1 # 出现次数为奇数的char可以留下一个，其他全部拿走
                one = True # 有char出现次数为奇数
        return res + one # 如果有char出现次数为奇数，我们可以把它放在Palindrome的中间，比如'accca'