409.Longest Palindrome

Tags: [map], [trick]

Link: https://leetcode.com/problems/longest-palindrome/?tab=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.

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.

Solution: map, trick

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0

        char_counting_map = {}
        for c in s:
            if c in char_counting_map:
                char_counting_map[c] += 1
            else:
                char_counting_map[c] = 1

        num_of_odd_num_chars = 0
        for k in char_counting_map:
            if char_counting_map[k] & 1 == 1:
                num_of_odd_num_chars += 1

        if num_of_odd_num_chars:
            return len(s) - num_of_odd_num_chars + 1
        else:
            return len(s)

Revelation:

• Sometimes, we don't need to build the real palindrome, because the question requires only the length of the longest palindrome, we just need to see the feature of the number of each chars.

• If the number of the chars is even, we can use all of them to build the palindrome, if the number of the chars is odd, we can use the even number of chars from them. For example, we have 'aaa', there are three 'a', we can use two of them, so which means, when we build the longest palindrome, if there is no odd number of chars, the max length of the palindrome is equal to the length of given string. If there exists the odd number of chars, for each odd-number chars, there is one of them we cannot use, but we can use remaining of them, and finally, if there exists odd-number chars, we still can use one of odd-number chars, putting it in the middle of the built longest palindrome.

• For example, the given s = 'eeeabaacccccddde', {'e': 4, 'a': 3, 'b': 1, 'c': 5, 'd': 3}, so we can use them build the longest palindromes are: 'eeadccaccdaee', or 'eeadccbccdaee', or 'eeadcccccdaee'.

Note:

• Time complexity = O(n), n is the number of chars in the given s.