題目

難度：★☆☆☆☆
類型：字符串

給定一個包含大寫字母和小寫字母的字符串，找到通過這些字母構造成的最長的回文串。

在構造過程中，請注意區(qū)分大小寫。比如 "Aa" 不能當做一個回文字符串。

注意

假設字符串的長度不會超過 1010。

示例

輸入:
"abccccdd"
輸出:
7

解釋:
我們可以構造的最長的回文串是"dccaccd", 它的長度是 7。

解答

方案1：使用計數器

這道題與最長回文子串題不同，要簡單很多，題目中所給出的字符串，更像一個字符的集合，我們無需考慮其出現的先后順序，因此，我們可以僅僅根據每個字符出現的個數計算出題目中的結果。

1. 如果字符串中所有字符均只出現過歐數次，那么組成回文串的最大長度和輸入字符串相等；

2. 對于任意一個字符，我們如果出現次數為偶數，那么我們就使用該字符所有的出現次數，如果是奇數，我們需要取不大于其出現次數的最大偶數；

3. 如果字符串中存在字符出現過奇數次，那么組成回文串后，出現過奇數次的字符中多余的字符可以放在最中間，在原始結果的基礎上加一，因此我們需要一個變量（odd_flag），探測是否有字符出現過奇數次；

from collections import Counter


class Solution:
    def longestPalindrome(self, s: str) -> int:
        counter = Counter(s)            # 統(tǒng)計s中各個字符出現的次數

        res, odd_flag = 0, 0            # 最終結果，出現基數次flag設置成為0
        for k, v in counter.items():    # 對于每一條統(tǒng)計記錄
            res += (v // 2) * 2         # 加上該字符成對出現最大數量
            if v % 2 == 1:              # 只要有一個字符的出現次數是奇數
                odd_flag = 1            # 最后結果就是要+1的
        return res + odd_flag           # 返回結果

這里有個列表版本計數器，道理類似：

class Solution:
    def longestPalindrome(self, s: str) -> int:
        counter = [0] * 58
        for x in s:
            counter[ord(x) - ord('A')] += 1
        res, odd_flag = 0, 0
        for n in counter:
            if n % 2 == 1:
                res += n - 1
                odd_flag = 1
            else:
                res += n
        return res + odd_flag

方法2：不用計數器

# 一對一對取出，如果是單著的，選一個就行
def longestPalindrome1_2(self, s):
    s_list = list(s)
    res, odd = 0, 0
    while s_list:
        c = s_list.pop()              # 彈出最后一個元素
        if c in s_list:               # 最后一個元素出現在剩下的元素中
            s_list.remove(c)          # 刪除相同的，相當于同時刪除了一對
            res += 2                  # 長度加2
        else:
            odd = 1                   # 選一個奇數的放中間
    return res + odd

如有疑問或建議，歡迎評論區(qū)留言~