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.

Intuition

A palindorme is a string with letters appear even number of times, plus possibly a unique center letter. For example, in abcba, letter a and b appear two times, and c is the unique letter.

If we want to build the longest palindorme, it consists of as many partnered letters as possible, plus a possible unique center letter.

Solution I

For each letter accours v times, if v is a even number, all of this letter can be partnered, if v is a odd number, then this letter could be the center letter, in this case, v can be added to final answers, otherwise, only v - 1 can be added.

The solution is quite simple, we count all the letters in the giving string, then look up the values in the counter, if v is even, add v to the final res, else add v - 1 to res, set single_num to 1 indicate that there is a center letter.

class Solution:
    def longestPalindrome(self, s: str) -> int:
        # cmap could be defined as:
        # cmap = collections.Counter(s)
        cmap = {}
        for c in s:
            cmap[c] = cmap.get(c, 0) + 1
        
        res, single_num = 0, 0
        for v in cmap.values():
            if v % 2 == 0:
                res += v
            else:
                res += v - 1
                single_num = 1
                
        return res + single_num

Solution II

Inspire by Discuss, we could simply just count how many letters appear an odd (or even) number of times, because we can use all letters, except for each odd-count letter we must drop one, and if there is a center letter, we can add 1 in at the end.

1-linear solutions:

1
2
3

# Count odds
def longestPalindrome(self, s: str) -> int:
    return len(s) - max(sum(v & 1 for v in collections.Counter.values()) - 1, 0)

1
2
3

# Count evens
def longestPalindrome(self, s: str) -> int:
    return min(sum(v & ~1 for v in collections.Counter(s).values()) + 1, len(s))

Complexity Analysis

Time Complexity: O(N), where N is the length of s. We need to count each letter.
Space Complexity: O(1), the space for our count, as the alphabet size of s is fixed.

Reference

https://leetcode.com/problems/longest-palindrome/discuss/89587/What-are-the-odds-(Python-and-C%2B%2B)