Leetcode 409 Longest Palindrome

Problem description

Leetcode 409

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.

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.

Problem Solving Process

To build the longest possible palindrome:

• Each character with an even frequency can be entirely used in the palindrome (since it contributes symmetrically to both halves).

• For characters with odd frequency, we can use all but one of their occurrences (i.e., count - 1) to maintain symmetry.

• Finally, if there exists at least one character with an odd frequency, we can place one remaining character in the center of the palindrome, adding +1 to the total length.

Code Implementation

def longestPalindrome(self, s):
    """
    :type s: str
    :rtype: int
    """
    if len(s) <= 1:
        return len(s)

    # Count character frequencies
    count = {}
    res = 0
    for char in s:
        count[char] = 1 + count.get(char, 0)
    
    # Sum usable pairs
    for v in count.values():
        if v % 2 == 0:
            res += v
        else:
            res += (v - 1)
    # If any odd frequency exists, one odd character can be placed in the middle
    if res < len(s):
        return res + 1
    else:
        return res

Complexity Analysis

• Time Complexity: O(n): Iterate string and count the frequency.

• Space Complexity: O(1): Without using extra data structure.