題目描述
給定一個(gè)包含大寫字母和小寫字母的字符串透揣，找到通過這些字母構(gòu)造成的最長的回文串婴渡。
在構(gòu)造過程中幻锁，請(qǐng)注意區(qū)分大小寫。比如 "Aa" 不能當(dāng)做一個(gè)回文字符串边臼。
注意:
假設(shè)字符串的長度不會(huì)超過 1010哄尔。
示例
示例 1：
輸入:
"abccccdd"
輸出:
7
解釋:
我們可以構(gòu)造的最長的回文串是"dccaccd", 它的長度是 7。
解答方法
方法一：貪心算法（哈希表）
思路
計(jì)算每個(gè)字符出現(xiàn)的次數(shù)柠并，取他的偶數(shù)倍岭接，出現(xiàn)次數(shù)為奇數(shù)的字符只加一次。
代碼
class Solution:
def longestPalindrome(self, s: str) -> int:
dic = collections.Counter(s)
res = 0
for L in dic.values():
res += L // 2 *2
if res % 2 == 0 and L % 2 ==1:
res +=1
return res
時(shí)間復(fù)雜度
O(N)臼予，其中 N為字符串 s 的長度鸣戴。我們需要遍歷每個(gè)字符一次。
空間復(fù)雜度
O(S)粘拾，其中 SS 為字符集大小窄锅。
