Longest Palindrome: Greedy Character Pairing

LeetCode 409, Longest Palindrome, asks a deceptively simple question: given a string of mixed-case letters, what is the longest palindrome you can build using those characters? You do not need to return the palindrome itself, just its length.

This is not the longest palindromic substring problem. That one asks you to find a palindrome hiding inside a string. This one gives you a bag of characters and asks you to construct the longest possible palindrome from scratch. Totally different approach.

The trick is recognizing that palindromes are built from pairs. Once you see that, the whole problem collapses into a frequency counter plus one small observation about odd counts.

The problem

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, so "Aa" is not a palindrome here.

Example: s = "abccccdd". The longest palindrome you can build is "dccaccd" (or any other valid arrangement), which has length 7.

Why 7 and not 8? Because 'a' and 'b' each appear once. You can use one of them in the center of the palindrome, but you cannot pair them. Every other character either has an even count (fully pairable) or contributes all-but-one to pairs.

The key insight: palindromes are made of pairs

Think about what makes a palindrome work. Every character on the left half has a matching character on the right half. That means every character in a palindrome (except possibly one in the dead center) must appear in pairs.

So the question becomes: how many pairs can I form from my character frequencies?

• A character with count 4 gives you 2 pairs (4 characters used).
• A character with count 3 gives you 1 pair (2 characters used), with 1 left over.
• A character with count 1 gives you 0 pairs, with 1 left over.

After collecting all pairs, if any character had a leftover (odd count), you can stick exactly one of those leftovers in the center. That adds 1 to your total.

That is the entire algorithm. Count frequencies, sum up the pairs, and check if you can add a center character.

The greedy solution

def longest_palindrome(s: str) -> int:
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1

    pairs = 0
    has_odd = False
    for count in freq.values():
        pairs += count // 2
        if count % 2 != 0:
            has_odd = True

    return pairs * 2 + (1 if has_odd else 0)

Let's break each piece down:

• Build the frequency map. Walk through every character and count how many times it appears. This is the same frequency counter pattern you used in Valid Anagram.
• Count pairs. For each character's frequency, count // 2 gives the number of pairs. A count of 5 yields 2 pairs (using 4 characters). A count of 1 yields 0 pairs.
• Track odd leftovers. If any count is odd, at least one character is left over after pairing. We can place exactly one leftover in the center of the palindrome.
• Compute the result. Each pair contributes 2 characters. If there is any odd leftover, add 1 for the center.

One pass to count, one pass over the frequency values. Done.

Step-by-step walkthrough

Let's trace through s = "abccccdd" to see how the character pairing greedy approach works.

The greedy character pairing approach processes each frequency independently. There is no interaction between characters. Each one contributes its pairs, and we check once at the end whether any odd leftovers exist.

Alternative: even simpler with set

There is a slick alternative that uses a set instead of a full frequency map. The idea: toggle characters in and out of a set. Every time you remove a character (meaning you have seen it twice), that is one pair.

def longest_palindrome(s: str) -> int:
    odd_chars = set()
    pairs = 0
    for ch in s:
        if ch in odd_chars:
            odd_chars.remove(ch)
            pairs += 1
        else:
            odd_chars.add(ch)

    return pairs * 2 + (1 if odd_chars else 0)

This does the same thing in a single pass without building a frequency map. At the end, odd_chars contains every character that appeared an odd number of times. If the set is non-empty, we can place one in the center.

Both solutions are O(n) time and O(1) space (since the character set is bounded). The frequency map version is easier to explain in an interview. The set version is more elegant but slightly harder to reason about on the spot.

Complexity analysis

*Space is O(1) because the character set is bounded (52 letters: 26 lowercase + 26 uppercase). If the input could contain arbitrary Unicode, space would be O(k) where k is the number of distinct characters.

Both approaches make a single pass through the string. The frequency map approach adds a second pass over the (at most 52) frequency values, but that is constant work.

Edge cases

All characters the same. s = "aaaa" gives 2 pairs = length 4. The entire string is already a palindrome.

All characters distinct. s = "abcde" gives 0 pairs, but we have odd leftovers, so the answer is 1. You can build a "palindrome" of length 1 from any single character.

Single character. s = "a" gives length 1. Trivial, but make sure your code handles it.

Mixed case. s = "Aa" gives 0 pairs (since 'A' and 'a' are different characters). The answer is 1, not 2. Case sensitivity is the most common mistake on this problem.

Empty string. s = "" gives 0. The frequency map is empty, has_odd is False, result is 0.

The building blocks

This problem is built from one core building block that shows up across many LeetCode problems.

Frequency counter

The act of walking through a collection and counting how many times each element appears:

freq = {}
for item in collection:
    freq[item] = freq.get(item, 0) + 1

In this problem, the frequency counter is the entire first half of the algorithm. You count character occurrences, then make a greedy decision based on those counts. The same micro-pattern appears in:

• Valid Anagram: count characters in both strings, compare counts
• Group Anagrams: use frequency counts (or sorted strings) as hash keys for grouping
• Top K Frequent Elements: count frequencies, then extract the k most common
• Minimum Window Substring: maintain a frequency map inside a sliding window

The frequency counter is one of the three core hash map patterns. If you have read the Hash Map Patterns post, this is Pattern 1 applied to a greedy problem instead of a comparison problem.

Why this problem is worth drilling

Longest Palindrome is an "easy" on LeetCode, and it feels easy when you read the solution. But the frequency counter building block is load-bearing. It is the same code you will write inside sliding window problems, anagram checkers, and bucket sort setups. If you can type the frequency counter template from scratch without thinking, you are free to focus on the harder parts of those problems instead of re-deriving the counting loop.

The greedy observation (pairs + optional center) is also worth internalizing. It is a small logical step, but the kind of thing that takes 30 seconds in an interview if it is already in your head, and 5 minutes if you have to re-derive it under pressure.

Related posts

• Valid Anagram - The simplest frequency counter problem, using the same counting pattern to compare two strings
• Valid Palindrome - The two pointer palindrome check, a different problem that tests palindrome structure from the reading side rather than the building side
• Hash Map Patterns - Frequency counting is one of the three core hash map techniques, and this problem is a clean example of it