Longest Palindrome LeetCode 409 Guide

LeetCode 409 — Longest Palindrome — gives you a string consisting of uppercase and lowercase letters and asks for the length of the longest palindrome that can be built with those characters. You do not have to use all characters, but you cannot add new ones. The answer is an integer — the maximum length, not the string itself.

For example, given "abccccdd", the answer is 7. One valid palindrome is "dccaccd": the four c's form the mirrored pairs in the middle, the two d's form the outer pair, and one of the a's or b's sits at the center. You leave behind one of a or b unused.

The problem is rated Easy but is a foundational string problem that teaches the core palindrome structure insight: every palindrome is symmetric, which means characters must appear in pairs — with at most one character allowed at the center.

A palindrome reads the same forwards and backwards. This mirrored structure means every character must appear on both sides of the palindrome — except for at most one character that can sit at the exact center. Any character with an even count can contribute all of its occurrences as symmetric pairs. Any character with an odd count can contribute count-1 occurrences as pairs, leaving one leftover.

Even-count characters are maximally efficient: every occurrence contributes to the palindrome. Odd-count characters waste exactly one occurrence — the unpaired remainder. The key insight is that at most one of those remainders can be rescued: you can place exactly one character at the center position, turning an odd-length or even-length structure into a palindrome.

This structural observation converts the problem into pure arithmetic: sum all even counts, add count-1 for each odd count (rounding down to the nearest even), then add 1 if any character had an odd count (to use one remainder as the center).

The algorithm starts by counting the frequency of every character in the string. In Python this is a one-liner with Counter; in Java you use a HashMap<Character, Integer> or a fixed-size array of 128 (covering all ASCII characters). Since the problem is case-sensitive, 'A' and 'a' are counted separately.

Once you have the frequency map, iterate over the counts. For each count, add count // 2 * 2 to the result — this is the largest even number less than or equal to count, representing all the pairs you can form. Simultaneously, track whether any count is odd using a boolean flag has_odd.

After the loop, if has_odd is true, add 1 to the result to account for the single center character. The final result is the maximum palindrome length.

At most one character can occupy the center position of a palindrome. In "aba" the center is 'b'; in "abba" there is no center (it is even-length). The center is what allows a palindrome to have odd total length — and it is always a single character with an odd frequency.

The has_odd flag captures this elegantly. If any character had an odd frequency, at least one remainder exists. You pick exactly one of those remainders as the center and add 1 to the total. It does not matter which character you choose for the center — any odd-count character's leftover works. The formula automatically maximizes the length.

Notice that even if five different characters each had odd counts, you can only use one of those five remainders as the center. The other four remainders are simply discarded. This is why the adjustment is always +1 at most, regardless of how many odd-count characters exist.

Consider the input "abccccdd". First build the frequency map: a=1, b=1, c=4, d=2. Now apply the formula: for c (count=4), add 4 (even, no waste); for d (count=2), add 2; for a (count=1), add 0 (count-1=0) and set has_odd=true; for b (count=1), add 0 and has_odd remains true.

Running total of pairs: 0 (from a) + 0 (from b) + 4 (from c) + 2 (from d) = 6. Since has_odd is true, add 1 for the center. Final answer: 7. One valid palindrome: "dccaccd" — d pairs wrap the outside, c pairs form the inner body, one 'a' sits at center. The lone 'b' is discarded.

Verification: length of "dccaccd" is 7. The two d's (one pair), the four c's (two pairs), and one center a account for 2 + 4 + 1 = 7 characters. Correct.

Python solution uses Counter for frequency counting, then iterates the values. The core loop: result += count // 2 * 2 for each count; set has_odd if count % 2 == 1. After the loop, return result + (1 if has_odd else 0). Time complexity O(n) for counting and iterating; space complexity O(1) since there are only 52 possible characters (a-z, A-Z). Java uses a HashMap or int[128] for ASCII, same logic.

A Python one-liner alternative: sum(c // 2 * 2 for c in Counter(s).values()) + (1 if any(c % 2 for c in Counter(s).values()) else 0). This computes the pair sum and center addition in two passes but is slightly less efficient due to the double Counter call. The loop version is cleaner and more readable.

Both Python and Java implementations run in O(n) time where n is the string length. The space is O(1) — bounded by the alphabet size (52 for this problem), not the input size. This is optimal since you must read each character at least once.

LeetCode 409 belongs to the palindrome construction family — problems that ask you to build or validate palindromes using character frequencies. Valid Palindrome II (LeetCode 680) is a close relative: given a string, can you remove at most one character to make it a valid palindrome? It tests the palindrome two-pointer approach combined with a greedy single-deletion attempt.

Longest Palindromic Substring (LeetCode 5) is a harder cousin: instead of counting characters freely, you must find the longest contiguous palindromic substring within a fixed string. It requires expanding around centers or Manacher's algorithm — a fundamentally different approach. Palindrome Partitioning (LeetCode 131) extends this to dynamic programming, asking for all ways to split a string into palindromic parts.

The frequency-counting pattern from LeetCode 409 also appears in palindrome construction variants: given k strings, can you rearrange their characters to form k palindromes? The core insight is always the same — count frequencies, pair up even counts, and manage at most one center per palindrome.