Given a string return the longest palindrome that can be constructed by removing or shuffling characters.
Example:
'aha'->'aha'
'ttaatta'->'ttaaatt'
'abc'->'a' or 'b' or 'c'
'gggaaa'->'gaaag' or 'aggga'
給出一個(gè)字符串咆畏，允許刪除字符和任意調(diào)換字符串位置，返回其最長的回文字符串善绎。假如有多種可能档泽，返回任意一種权埠。
1. 詢問
字符串問題，還是要問一下字符類型。假如還是什么字符都有可能戏锹。
2. 分析
暴力破解
暴力破解就是列出所有可能的字符串贯溅，然后判斷是不是回文串拄氯，最后返回最長的那個(gè)。復(fù)雜度非常高它浅。
如何改進(jìn)
暴力破解之所以低效译柏，是因?yàn)闆]有利用回文字符串的特點(diǎn)，在不可能構(gòu)成回文字符串的情況下繼續(xù)去試姐霍，在可以構(gòu)成回文字符串的情況下不能馬上得出結(jié)果鄙麦。
回文字符串有一個(gè)很鮮明的特點(diǎn)，整個(gè)字符串可以分成L-M-R邮弹，其中L和R部分對稱黔衡，M可以是單個(gè)字符也可以是空字符。因此腌乡，對回文字符串的字母頻數(shù)計(jì)數(shù)盟劫，可以知道最多只能有1種字母的頻數(shù)為奇數(shù)，對應(yīng)M是單個(gè)字符的情況与纽；假如M是空字符侣签，那么所有頻數(shù)都是偶數(shù)。
回到本題急迂，按照上面的思路影所，先對字符串的字母進(jìn)行計(jì)數(shù)，O(n)僚碎。因?yàn)橐铋L的猴娩，因此希望能夠盡量少刪除。假如有多個(gè)字母的計(jì)數(shù)為奇數(shù)，只能留下一個(gè)奇數(shù)卷中，剩余的奇數(shù)字符桩警，都需要舍棄掉1個(gè)然后當(dāng)做偶數(shù)處理塘秦。
之后就是構(gòu)造了陋气，還是按照L-M-R的思路來溉跃，先把M放了，同時(shí)奇數(shù)的那個(gè)字符-1十减，假如沒有就放空字符栈幸。這樣剩下的都按照偶數(shù)處理，然后先造一邊帮辟，所有字符取一半放在一起速址，再逆序放到另外一邊即可。還是O(n)由驹。
因此壳繁，整體的時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)荔棉。
3. 代碼
class Solution:
def longestPalindrome(self, s):
if not s:
return ''
d = {}
L, M = '', ''
# count chars and let M point to an odd count char else empty
for c in s:
if c not in d:
d[c] = 1
M = c
else:
d[c] += 1
if d[c] & 1:
M = c
else:
if M == c:
M = ''
if M:
d[M] -= 1
for k, v in d.items():
if v:
L += k * (v // 2)
return L + M + L[::-1]
4. 總結(jié)
難度medium。其實(shí)掌握回文字符串的特性蒿赢，這個(gè)問題就迎刃而解了润樱。
