题目

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。

示例 1:

  1. 输入:
  2. "abccccdd"
  3. 输出:
  4. 7
  5. 解释:
  6. 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

答案1 贪心

#
# @lc app=leetcode.cn id=409 lang=python3
#
# [409] 最长回文串
#

# @lc code=start

import collections


class Solution:
    def longestPalindrome(self, s: str) -> int:
        ans = 0
        count = collections.Counter(s)
        for v in count.values():
            # 对于每个字符 ch，假设它出现了 v 次，我们可以使用该字符 v / 2 * 2 次，
            # 在回文串的左侧和右侧分别放置 v / 2 个字符 ch，其中 / 为整数除法。例如若 "a" 出现了 5 次，
            # 那么我们可以使用 "a" 的次数为 4，回文串的左右两侧分别放置 2 个 "a"。

            # 如果有任何一个字符 ch 的出现次数 v 为奇数（即 v % 2 == 1），
            # 那么可以将这个字符作为回文中心，注意只能最多有一个字符作为回文中心。
            # 在代码中，我们用 ans 存储回文串的长度，由于在遍历字符时，ans 每次会增加 v / 2 * 2，因此 ans 一直为偶数。
            # 但在发现了第一个出现次数为奇数的字符后，我们将 ans 增加 1，这样 ans 变为奇数，
            # 在后面发现其它出现奇数次的字符时，我们就不改变 ans 的值了。
            ans += v // 2 * 2
            if ans % 2 == 0 and v % 2 == 1:
                ans += 1
        return ans


Solution().longestPalindrome("abccccdd")
# @lc code=end