409.longest-palindrome

Statement

简体中文English

Metadata

• Link: 最长回文串
• Difficulty: Easy
• Tag: 贪心 哈希表 字符串

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

 

示例 1:

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

输入:s = "a"
输入:1

示例 3:

输入:s = "bb"
输入: 2

 

提示:

• 1 <= s.length <= 2000
• s 只能由小写和/或大写英文字母组成

Metadata

• Link: Longest Palindrome
• Difficulty: Easy
• Tag: Greedy Hash Table String

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

 

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a"
Output: 1

Example 3:

Input: s = "bb"
Output: 2

 

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase and/or uppercase English letters only.

Solution

Python 3

from collections import Counter


class Solution:
    def longestPalindrome(self, s: str) -> int:
        c = Counter(s)
        odd = 0
        res = 0
        for v in c.values():
            res += v // 2 * 2
            if v & 1:
                odd = 1
        return res + odd

---

最后更新: October 11, 2023