0%

[Leetcode]409. Longest Palindrome (C++)

题目描述

题目链接:409. Longest Palindrome

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

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

例子

例子 1

Input: “abccccdd”
Output: 7
Explanation: One longest palindrome that can be built is “dccaccd”, whose length is 7.

解题思路

这道题需要找的是用所有字母能组成的最长回文的长度,那么思路很简单,统计所有字母出现的个数,偶数个的放两侧(对称),奇数个的拿掉一个放中间,剩余放两侧,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int longestPalindrome(string s) {

std::unordered_map<char, int> count_letter;

for (const char& letter: s) {
count_letter[letter]++;
}

int length = 0;
bool has_odd = false;
for (auto iter = count_letter.begin(); iter != count_letter.end(); iter++) {
if (iter->second % 2) has_odd = true;
length += iter->second % 2 == 0 ? iter->second : iter->second - 1;
}

if (has_odd) length += 1;

return length;

}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)