FXTi's blog
0%

longest-palindrome

Posted on Edited on

Longest Palindrome – LeetCode 409

Problem

Description

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.

Example

Input:
“abccccdd”

Output:
7

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

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int longestPalindrome(string s) {
        int count[128] = {0}, sum = 0;
        for(char &c: s)
            ++count[c];
        for(int &i: count){
            if(sum & 0x1)
                sum += i & ~0x1;
            else 
                sum += i;
        }
        return sum;
    }
};

思路

题目说是可以交换次数，于是就是多个偶数个加上一个奇数个。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$6$ ms，排名$79.53\%$

Better

思路

还没看到更好的思路。