给定一个包含大写字母和小写字母的字符串s,通过 这些字母构造成最长的回文串,并显示该回文串。
时间: 2024-05-05 08:16:04 浏览: 98
思路:可以使用一个字典记录每个字符出现的次数,然后将出现次数为奇数的字符加入回文串的中心,再将出现次数为偶数的字符左右分别放置在回文串两侧。最后将回文串拼接起来即可。
代码实现:
```python
def longestPalindrome(s: str) -> str:
if not s:
return ""
# 统计每个字符出现的次数
char_count = {}
for c in s:
if c in char_count:
char_count[c] += 1
else:
char_count[c] = 1
# 构造回文串
center = ""
left = ""
right = ""
for c, count in char_count.items():
if count % 2 == 0:
left += c * (count // 2)
right = c * (count // 2) + right
else:
center = c
left += c * (count // 2)
right = c * (count // 2) + right
return left + center + right
```
测试:
```python
>>> longestPalindrome("abccccdd")
'dccaccd'
>>> longestPalindrome("abcde")
'e'
>>> longestPalindrome("AaBbcCdd")
'ddccbBAa'
```
阅读全文