最长回文串

by ·0 Comments

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

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

样例
给出 s = “abccccdd” 返回 7

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

思路：回文串的特性是对称性。若想构造回文串，只需将原字符串中数量为偶数个的元素放置在回文串两边，将某个数量为奇数个元素的元素放置在回文串正中间即可。题目的要求是构造最长回文串。那么我们可以对原字符串进行分解并统计其中每个元素出现的次数。若出现偶数次，则不用处理，直接放在新字符串两边即可；若出现奇数次，则可以减1放在新字符串两边；同时，原字符串内出现奇数次最多的元素可以放在新字符串正中间。同时满足这三个要求，即是最长回文串。

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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):
        if s == '':
            return 0
        var = set(s)
        n = 0                                                 #n为新字符串中放置在两边的偶数元素
        m = 1                                                 #m为新字符串放置在正中间的奇数元素
        t = -1                                                #t为最多个奇数元素出现的次数（如aaabbbccc这种情况下，t=3）
        if len(var) == 1:
            return len(s)
        for i in var:
            if s.count(i) % 2 != 0 and s.count(i) > m:
                m = s.count(i)
        for i in var:
            if s.count(i) % 2 == 0:
                n += s.count(i)
            elif s.count(i) == m:
                t += 1
            else:
                n += s.count(i)-1
        return n+m+(m-1)*t

解法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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):
        if s == '':
            return 0
        var = set(s)
        if len(var) == 1:
            return len(s)
        total = len(s)
        for i in var:
            if s.count(i) % 2 != 0:                            #简单优雅，遇到奇数直接减一
                total -= 1
        return total+1