LeetCode 409 - Longest Palindrome

The problem asks us to find the length of the longest palindrome that can be constructed using the characters of a given string s. A palindrome is a string that reads the same forwards and backwards.

leetcodeeasyhash-tablestringgreedy

LeetCode Problem 409

Difficulty: 🟢 Easy
Topics: Hash Table, String, Greedy

Solution

Problem Understanding

The problem asks us to find the length of the longest palindrome that can be constructed using the characters of a given string s. A palindrome is a string that reads the same forwards and backwards. The input string s contains only lowercase and uppercase English letters, and letter case matters, so 'A' and 'a' are distinct characters. The output is a single integer representing the maximum length of a palindrome we can form.

For example, if the input is "abccccdd", one possible palindrome is "dccaccd", which has a length of 7. This demonstrates that the solution does not need to return the actual palindrome, only its length.

Key constraints are that the string length is between 1 and 2000, which allows us to consider solutions with linear or near-linear time complexity. Edge cases include a string with all unique characters, a string with all identical characters, or a string of length 1.

Approaches

A brute-force approach would involve generating all permutations of the string and checking if each permutation is a palindrome, then tracking the longest. This guarantees a correct answer because it exhaustively searches all possibilities. However, the time complexity is factorial, O(n!), making it infeasible for n = 2000.

The key observation for an optimal solution is that a palindrome can use pairs of characters symmetrically on either side. Characters that appear an even number of times can fully contribute to the palindrome, while characters with odd counts can contribute count - 1. We can also place one single character with an odd count in the middle, increasing the palindrome length by 1.

We can use a hash map (or dictionary) to count the occurrences of each character, iterate through the counts, sum the even contributions and track if any odd count exists for the center placement. This reduces the problem to O(n) time and space complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Generates all permutations and checks each for palindrome
Optimal O(n) O(n) Count characters and sum pairs, with optional center for odd count

Algorithm Walkthrough

  1. Initialize a hash map (dictionary) to count the frequency of each character in the string s.
  2. Iterate over the string s, updating the count for each character in the map.
  3. Initialize a variable length to 0. This will store the total length of the palindrome.
  4. Initialize a boolean flag odd_found to False, which will indicate if we have any character with an odd count.
  5. Iterate over all character counts:
  • If the count is even, add it directly to length because it can fully contribute to the palindrome.
  • If the count is odd, add count - 1 to length to include the largest even portion. Set odd_found to True.
  1. After processing all counts, if odd_found is True, increment length by 1 to account for a central character.
  2. Return length as the length of the longest palindrome.

Why it works: This algorithm ensures that all pairs of characters are used symmetrically around the center. At most one odd character can occupy the middle, which is why we increment by 1 if any odd counts exist. The approach guarantees maximal length because every character contributes to the palindrome either fully (even counts) or maximally minus one (odd counts).

Python Solution

class Solution:
    def longestPalindrome(self, s: str) -> int:
        from collections import Counter
        
        char_count = Counter(s)
        length = 0
        odd_found = False
        
        for count in char_count.values():
            if count % 2 == 0:
                length += count
            else:
                length += count - 1
                odd_found = True
        
        if odd_found:
            length += 1
        
        return length

This Python implementation uses Counter to efficiently count characters. The loop over counts distinguishes between even and odd occurrences, summing pairs to length. The odd_found flag ensures that a single odd-count character can be placed in the center.

Go Solution

func longestPalindrome(s string) int {
    charCount := make(map[rune]int)
    for _, ch := range s {
        charCount[ch]++
    }
    
    length := 0
    oddFound := false
    
    for _, count := range charCount {
        if count%2 == 0 {
            length += count
        } else {
            length += count - 1
            oddFound = true
        }
    }
    
    if oddFound {
        length++
    }
    
    return length
}

In Go, we use a map[rune]int to count characters. Iterating over s as runes ensures proper handling of each character. The logic mirrors Python, handling even and odd counts and adding a central character if needed.

Worked Examples

Example 1: "abccccdd"

Character Count Contribution Length
a 1 0 (odd) 0
b 1 0 (odd) 0
c 4 4 (even) 4
d 2 2 (even) 6

odd_found = True → add 1 → length = 7

Example 2: "a"

Character Count Contribution Length
a 1 0 (odd) 0

odd_found = True → add 1 → length = 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Counting characters and iterating through counts is linear in the length of s
Space O(n) Storing counts of each character in a hash map requires space proportional to the unique characters in s

Since the input string is limited to uppercase and lowercase letters, space is bounded by 52 at most.

Test Cases

# Basic examples
assert Solution().longestPalindrome("abccccdd") == 7  # Example with multiple pairs
assert Solution().longestPalindrome("a") == 1         # Single character

# Edge cases
assert Solution().longestPalindrome("abc") == 1       # All unique characters
assert Solution().longestPalindrome("aa") == 2        # All same characters
assert Solution().longestPalindrome("Aa") == 1        # Case sensitivity check

# Mixed cases
assert Solution().longestPalindrome("abABabAB") == 8  # Pairs of upper/lowercase letters
assert Solution().longestPalindrome("aaaabbbbccccddde") == 13  # Odd + even mix
Test Why
"abccccdd" Standard case with even and odd counts
"a" Single character
"abc" All characters unique, longest palindrome is length 1
"aa" All characters same, contributes fully
"Aa" Case sensitive, cannot pair 'A' and 'a'
"abABabAB" Mixed cases, multiple pairs
"aaaabbbbccccddde" Mix of odd and even counts, tests odd central character logic

Edge Cases

Single character string: If s has only one character, the palindrome length is 1. This is handled by initializing length = 0 and adding 1 if any odd count exists.

All characters unique: If every character appears only once, the longest palindrome is length 1, as only one character can be in the center. The algorithm correctly identifies a single odd count and adds 1.

Case sensitivity: Characters like 'A' and 'a' are distinct. Counting them separately ensures the algorithm does not mistakenly pair them, preserving correctness for mixed-case inputs.

This approach handles all other combinations of odd and even counts systematically, guaranteeing the maximal palindrome length for any valid string.