LintCode 627.最长回文串

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 507 阅读时长 ≈ 2 分钟

题意

给出一个包含大小写字母的字符串。求出由这些字母构成的最长的回文串的长度是多少。

数据是大小写敏感的，也就是说，"Aa" 并不会被认为是一个回文串。

注意事项

假设字符串的长度不会超过 1010。

样例

给出 s = "abccccdd" 返回 7

一种可以构建出来的最长回文串方案是 "dccaccd"。

思路

看到题目，第一个关键是看到，这道题只要求长度即可，不需要求出具体的回文串，所以会方便很多。

既然只要求出长度，那么一定是有一些简单的方法算出来不用求出具体的回文串到底如何的。

那我们就思考，要组成回文串需要什么样的条件呢？

  1. 单个字母，放在回文串中间，一定是回文串
  2. 两个相同的字母，一定能组成回文串
  3. 两个或者多个不同的字母，一定不能组成回文串

这里的关键是第二点，两个相同的字母一定能组成回文串，所以我们就先考虑一下，如果一个字母在给定字符串中出现了偶数次数，那么一定能组成回文串。

那如果一个字母出现了奇数次呢？

思考一下就能想到，奇数次的出现次数，等于偶数次+1。

根据上面的第一和第三点，如果说有出现奇数次的字母，那么这些字母中可以选择一个放在回文串中间，这样长度可以+1。

最后剩下的就是一些边界情况处理了，比如，如果所有的字母都出现偶数次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    """
    @param s: a string which consists of lowercase or uppercase letters
    @return: the length of the longest palindromes that can be built
    """
    def longestPalindrome(self, s):
        odd = list()
        for ch in s:
            if ch not in odd:
                odd.append(ch)
            else:
                odd.remove(ch)

        num = len(odd)
        if num > 0:
            num -= 1
        return len(s) - num