LeetCode 409: Longest Palindrome

Problem Description

LeetCode Problem 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.

Difficulty: Easy

Tags: hash table, string, greedy

Rating: 93.46%

Solution

Here’s my Python solution to this problem:

#Problem 409: Longest Palindrome

class Solution:
    def longestPalindrome(self, s: str) -> int:
        count = {}
        for c in s: 
            count[c] = count.get(c, 0) + 1

        l = 0
        has_odd = False

        for c in count.values():
            l += (c//2)*2
            if c % 2 == 1:
                has_odd = True
        
        return l + 1 if has_odd else l

Complexity Analysis

The solution has the following complexity characteristics:

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Note: This is an automated analysis and may not capture all edge cases or specific algorithmic optimizations.