zkkKillua's Blog
0%

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.

Example:

Input:
“abccccdd”

Output:
7

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

框架

1
2
3
4
5
6
class Solution {
public:
    int longestPalindrome(string s) {

    }
};

1. 统计次数

回文串中所有的同一类的字符必为偶数个，再加上可能有的最中间的那个字符。
每个字符遍历一次，O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int longestPalindrome(string s) {
        int count[52];
        for (int i = 0; i < 52; i++)
            count[i] = 0;
        int ans = 0;

        int lenS = s.length();
        for (int i = 0; i < lenS; i++) {
            if (s[i] >= 'a' && s[i] <= 'z')
                count[s[i] - 'a']++;
            else
                count[s[i] - 'A' + 26]++;
        }

        for (int i = 0; i < 52; i++) {
            if (count[i] % 2 == 0)
                ans += count[i];
            else
                ans += count[i] - 1;
        }
        if (ans < lenS)
            ans++;
        
        return ans;
    }
};