最长回文串
https://www.lintcode.com/problem/627/?utm_source=sc-che
描述
给出一个包含大小写字母的字符串。求出由这些字母构成的最长的回文串的长度是多少。
数据是大小写敏感的,也就是说,"Aa"
并不会被认为是一个回文串。
假设字符串的长度不会超过 100000
。
样例
样例 1:
输入 : s = "abccccdd"输出 : 7说明 : 一种可以构建出来的最长回文串方案是 "dccaccd"。
将字符串中的每个字符出现的次数记录下来。
对于每个字符,如果其出现次数为偶数,则可以将这些字符全部用在回文串中。
如果出现次数为奇数,则可以取这些字符的最大偶数部分。
最后,如果有字符出现次数为奇数,可以再在回文串中心添加一个这样的字符。
```python 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 longest_palindrome(self, s: str) -> int: # write your code here #贪心,统计所有字母的个数。但凡有偶数都使用,奇数的字母任选一个做中心。 # 记得奇数的字母依然全部使用。只需要任选一次中心 res = 0 count = collections.Counter(s) #库函数!!!!!! for v in count.values(): res += v//2*2 #贪心 有多少偶数都收入 if v % 2 == 1 and res % 2 == 0: #有且仅有一次,当前字母是奇数,且结果是偶数可容纳一次奇数。 res += 1 return res ```
Last updated
Was this helpful?