LeetCode 409: Longest Palindrome Solution in Python – A Step-by-Step Guide

What Is LeetCode 409: Longest Palindrome?

In LeetCode 409: Longest Palindrome, you’re given a string s (like "abccccdd"), and you need to find the length of the longest palindrome you can build by rearranging its characters. A palindrome needs pairs of letters (e.g., "aa" or "bb") for symmetry, and if you have any leftovers, you can stick one odd count in the middle (e.g., "aba"). For "abccccdd," you can make "dccbccd" (7 letters: 4 c’s, 2 d’s, 1 b in the middle). The catch? Case matters ("A" ≠ "a"), and you’re limited to the characters in the string.

Problem Statement

• Input: A string s.
• Output: An integer—the length of the longest palindrome possible.
• Rules:
• Use each character as many times as it appears.
• Pair characters for symmetry, add one odd count in the middle if available.

Constraints

• 1 <= s.length <= 10⁵.
• s contains uppercase and lowercase letters.

Examples

• Input: s = "abccccdd"
• Output: 7 (e.g., "dccbccd").
• Input: s = "a"
• Output: 1 (just "a").
• Input: s = "bb"
• Output: 2 ("bb").

Understanding the Problem: Building the Palindrome

To solve LeetCode 409: Longest Palindrome in Python, we need to figure out how many characters we can pair up (even counts) and if there’s an odd count to add in the middle. A naive idea might be to try every possible palindrome—but with up to 10⁵ characters, that’s way too slow! Instead, we’ll use:

• Best Solution (Hash Map with Counting): O(n) time, O(1) space—counts characters efficiently.
• Alternative Solution (Array-Based Counting): O(n) time, O(1) space—uses a fixed array.

Let’s dive into the hash map solution with a clear, step-by-step explanation.

Best Solution: Hash Map with Counting

Why This Is the Best Solution

The hash map with counting method is the top pick because it’s fast—O(n) time, O(1) space (since the character set is limited)—and super intuitive. It counts how many times each character appears, pairs them up for the palindrome’s sides, and adds one odd count in the middle if there’s any leftover. It’s like sorting your letter blocks into piles and building the longest mirror-word you can!

How It Works

Think of the string as a bag of letter blocks:

• Step 1: Count the Blocks:
• Use a hash map to tally each character (e.g., "a": 2, "b": 2, "c": 4, "d": 1).
• Step 2: Pair Them Up:
• For each character, take the even part of its count (e.g., 4 c’s → 4, 1 d → 0).
• Add these even counts to the length (pairs go on both sides).
• Step 3: Check for a Middle:
• If any character has an odd count, add 1 to the length (one can go in the center).
• Step 4: Why This Works:
• Even counts form symmetric pairs (e.g., "cc" in "dccbccd").
• One odd count can sit in the middle (e.g., "b" in "dccbccd").
• We maximize length by using all pairs and one extra if possible.

Step-by-Step Example

Example: s = "abccccdd"

• Count: {"a": 1, "b": 1, "c": 4, "d": 2}.
• Pairs:
• "a": 1 → 0 (even part).
• "b": 1 → 0.
• "c": 4 → 4.
• "d": 2 → 2.
• Length = 0 + 0 + 4 + 2 = 6.
• Middle: Odd counts (a, b), add 1.
• Total: 6 + 1 = 7.
• Result: 7 (e.g., "dccbccd").

Example: s = "aabbcc"

• Count: {"a": 2, "b": 2, "c": 2}.
• Pairs: 2 + 2 + 2 = 6.
• Middle: No odd counts, add 0.
• Total: 6.
• Result: 6 (e.g., "aabbcc").

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def longestPalindrome(self, s: str) -> int:
        # Step 1: Count characters
        char_count = {}
        for char in s:
            char_count[char] = char_count.get(char, 0) + 1

        # Step 2: Calculate length from pairs
        length = 0
        has_odd = False
        for count in char_count.values():
            length += (count // 2) * 2  # Even part (pairs)
            if count % 2 == 1:          # Check for odd
                has_odd = True

        # Step 3: Add middle if odd exists
        if has_odd:
            length += 1

        return length

• Line 4-6: Build hash map:
• Loop through s, count each char (e.g., "a": 1, "b": 1).
• Line 9-13: Compute length:
• Line 11: Add even part (count // 2 * 2) for pairs (e.g., 4 // 2 * 2 = 4).
• Line 12-13: Flag if any count is odd (e.g., 1 % 2 = 1).
• Line 16-17: If any odd, add 1 for middle.
• Line 19: Return total length.
• Time Complexity: O(n)—one pass through string.
• Space Complexity: O(1)—hash map size is fixed (52 letters max, a-z, A-Z).

This is like stacking letter blocks into a perfect mirror shape!

Alternative Solution: Array-Based Counting

Why an Alternative Approach?

The array-based counting method uses a fixed-size array instead of a hash map, counting characters by their ASCII values. It’s O(n) time and O(1) space too—simpler in some ways but less flexible. It’s like sorting your blocks into 52 labeled bins (one for each letter)!

How It Works

Picture it as a tally chart:

• Step 1: Use an array (size 52) for a-z and A-Z.
• Step 2: Count each character’s occurrences.
• Step 3: Sum even counts, add 1 if any odd.

Step-by-Step Example

Example: s = "abccccdd"

• Array: [1, 1, 4, 2, ...] (a, b, c, d at indices 0, 1, 2, 3).
• Pairs: 0 + 0 + 4 + 2 = 6.
• Odd: Yes (a, b), add 1.
• Total: 6 + 1 = 7.
• Result: 7.

Code for Array-Based Approach

Copy codeclass Solution:
    def longestPalindrome(self, s: str) -> int:
        # Step 1: Array for a-z (0-25) and A-Z (26-51)
        counts = [0] * 52

        # Step 2: Count characters
        for char in s:
            if char.islower():
                idx = ord(char) - ord('a')
            else:
                idx = ord(char) - ord('A') + 26
            counts[idx] += 1

        # Step 3: Calculate length
        length = 0
        has_odd = False
        for count in counts:
            length += (count // 2) * 2
            if count % 2 == 1:
                has_odd = True

        if has_odd:
            length += 1

        return length

• Time Complexity: O(n)—one pass.
• Space Complexity: O(1)—fixed 52-size array.

It’s a bin-sorting palindrome builder!

Comparing the Two Solutions

• Hash Map with Counting (Best):
• Pros: O(n), O(1), flexible and readable.
• Cons: Slightly more memory for hash.
• Array-Based Counting (Alternative):
• Pros: O(n), O(1), minimal memory.
• Cons: Fixed character set.

Hash map wins for clarity.

Additional Examples and Edge Cases

• "A": 1.
• "aa": 2.
• "": 0 (assumed per problem intent).

Hash map handles all.

Complexity Breakdown

• Hash Map: Time O(n), Space O(1).
• Array-Based: Time O(n), Space O(1).

Hash map’s versatile.

Key Takeaways

• Hash Map: Count smart!
• Array-Based: Bin it up!
• Palindromes: Pairs plus one.
• Python Tip: Dicts are handy—see [Python Basics](/python/basics).

Final Thoughts: Build That Palindrome

LeetCode 409: Longest Palindrome in Python is a letter-pairing adventure. Hash map counting stacks it up fast, while array-based bins it neatly. Want more string fun? Try LeetCode 5: Longest Palindromic Substring or LeetCode 647: Palindromic Substrings. Ready to pair? Head to Solve LeetCode 409 on LeetCode and build that palindrome today!