Problem Statement

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.

Examples

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
Explanation: The longest palindrome that can be built 
is "a", whose length is 1.

Constraints

  • 1 <= s.length <= 2000
  • s consists of lowercase and/or uppercase English letters only.

Key Insights

A palindrome is a sequence of characters that spell out the same word read forwards or backwards, i.e. tot. A palindrome has symmetry about the vertical axis. There are two different types of palindrome. The first one has an odd number of characters "aabcbaa" and the second has an even number of characters "aabbaa".

Since the problem asks us to determine the length of the longest palindrome, we simply need to determine the frequency of each character in the string. If a character appears an odd number of times in the string, we know that it can be used as the center element.

If a character appears an even number of times, we know that it will appear on either side of the axis of symmetry (the middle in plain english).

To begin with, we can loop over the string and construct a hash map whose keys are the characters and whose values are the frequencies. Once we have this hash map, we can loop over it one more time and count the number of even letter pairs and add them to the ans. We also need to figure out if any character appears an odd number of times. If one or more characters appears an odd number of times we need to take note of that fact and add 1 to the final ans.

As we loop over the hash map, we can employ integer division, i.e. 2 * (9 // 2) = 8 to determine the number of characters that can contribute to even pairs in the string. We can use a flag to keep track of the discovery of any characters which have odd frequencies that could be used at the center character.

Python Solution

from collections import Counter
class Solution:
    def longestPalindrome(self, s: str) -> int:
        """
            T: O(N)
            S: O(N)
        """
        # Create a character-frequency hash map
        mp = Counter(s)
        ans = 0
        flag = 0

        # Loop over the hash map count the number of 
        # character that contribute to even pairs.
        # Keep track of the presence of characters that have
        # odd frequencies and add 1 to the final result
        # if applicable.
        for key, val in mp.items():
            # If a character with an odd frequency occurs in
            # the string, set the flag to 1. We know that
            # we will have a center value.
            if val % 2 == 1:
                flag = 1

            # Integer division "//" rounds down to the
            # nearest integer. Multiplying the result by
            # 2 gives use the number of characters
            # contributed by character pairs.
            # "aaa" -> 2*(3//2) = 2*1 
            ans += 2 * (val // 2)

        if flag:
            return ans + 1
        else:
            return ans