LeetCode409 Longest Palindrome

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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
2
3
4
5
6
7
8
Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

思路

问从输入的字符串中任意挑选出字符所能够组成的最长回文串的长度是多少。每个字符只能用一次,也可以不用。

一看题目还以为求最长回文子串,Manacher算法走起啊… 然而仔细看题并不是,其实只是一个模拟。首先统计出所有字符的个数,然后偶数个的通通加进来,奇数个的就扣掉一个变成偶数再加进来。注意,如果存在某个字符的个数是奇数的话,答案长度可以再加1,因为可以把这个字符放在中间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int longestPalindrome(string s) {
int cnt[26][2] = {0};
for (char& c: s) {
if (isupper(c)) cnt[c-'A'][0]++;
else cnt[c-'a'][1]++;
}
int ans = 0, add = 0, cur;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 2; ++j) {
cur = cnt[i][j];
if (cur & 1) add = 1;
ans += cur - (cur & 1);
}
}
return ans + add;
}
};
分享到 评论