No.0008-CareerCup

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'
给出一个字符串，允许删除字符和任意调换字符串位置，返回其最长的回文字符串。假如有多种可能，返回任意一种。

1. 询问

字符串问题，还是要问一下字符类型。假如还是什么字符都有可能。

2. 分析

暴力破解

暴力破解就是列出所有可能的字符串，然后判断是不是回文串，最后返回最长的那个。复杂度非常高。

如何改进

暴力破解之所以低效，是因为没有利用回文字符串的特点，在不可能构成回文字符串的情况下继续去试，在可以构成回文字符串的情况下不能马上得出结果。
回文字符串有一个很鲜明的特点，整个字符串可以分成L-M-R，其中L和R部分对称，M可以是单个字符也可以是空字符。因此，对回文字符串的字母频数计数，可以知道最多只能有1种字母的频数为奇数，对应M是单个字符的情况；假如M是空字符，那么所有频数都是偶数。
回到本题，按照上面的思路，先对字符串的字母进行计数，O(n)。因为要最长的，因此希望能够尽量少删除。假如有多个字母的计数为奇数，只能留下一个奇数，剩余的奇数字符，都需要舍弃掉1个然后当做偶数处理。
之后就是构造了，还是按照L-M-R的思路来，先把M放了，同时奇数的那个字符-1，假如没有就放空字符。这样剩下的都按照偶数处理，然后先造一边，所有字符取一半放在一起，再逆序放到另外一边即可。还是O(n)。
因此，整体的时间复杂度O(n)，空间复杂度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. 总结

难度medium。其实掌握回文字符串的特性，这个问题就迎刃而解了。