409. Longest Palindrome

2020, Nov 27 2 mins read

1. Description

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.
Letters are case sensitive, for example, “Aa” is not considered a palindrome here.

2. Example

Example 1

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

Example 2

Input: s = “a”
Output: 1

Example 3

Input: s = “bb”
Output: 2

3. Constraints

1 <= s.length <= 2000
s consits of lower-case and/or upper-case English letters only.

4. Solutions

Bit Manipulation

n = i_str.size()
Time complexity: O(n)
Space complexity: O(1)

 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
class Solution
{
public:
    // int longestPalindrome(string s)
    int longestPalindrome(string &i_str)
    {
        vector<int> letterTimes(256); // char set
        for(int i = 0; i < i_str.size(); i++)
            letterTimes[i_str[i]]++;

        // even number char could construct a palindrome
        int result = 0;
        for(int i = 0; i < letterTimes.size(); i++)
        {
            if(letterTimes[i] & 1)
                result += letterTimes[i] - 1;
            else
                result += letterTimes[i];
        }

        // we could add another char at the middle of the palindrome, but we shuold check whether we have enough chars
        // since all chars may have even numbers
        return min(result + 1, (int)i_str.size());
    }
};

Search

Tags