Longest Palindrome — Solution

Problem

Given a string of letters (uppercase and lowercase treated as distinct), return the length of the longest palindrome you can build using those characters. You don't need to return the palindrome itself — only its maximum possible length.

• Input: s = "abccccdd"
• Output: 7
• Explanation: One valid palindrome is "dccaccd" (length 7) — characters c×4, d×2, and one a in the middle.

Counter-example: s = "a" → output is 1. A single character is itself a valid palindrome.

Intuition

A palindrome reads the same forwards and backwards, so almost every character must appear in a matched pair (one on the left half, one mirroring it on the right). The only exception is the center position, which can hold any single character. Count how many characters appear an even number of times — those pairs can all be used. Characters with odd counts contribute their largest even portion (count - 1), and if any such odd-count character exists, we can donate one to the center.

Solution — Greedy Counting

Tally each character's frequency. For every character, take as many pairs as possible (its count rounded down to the nearest even number). If any character had an odd count, add 1 for the center slot.

1. Build a frequency map of every character in s.
2. Initialize length = 0.
3. For each frequency, add (frequency // 2) * 2 to length — this captures all complete pairs.
4. If length < len(s), at least one character had an odd count; add 1 for the center.
5. Return length.

1from collections import Counter
2
3def longestPalindrome(self, s: str) -> int:
4    char_counts = Counter(s)
5    length = 0
6
7    for count in char_counts.values():
8        length += (count // 2) * 2  # use every complete pair; discard the leftover if count is odd
9
10    if length < len(s):  # some character had an odd count, so we can place one in the center
11        length += 1
12
13    return length

Time: O(n) — one pass to count frequencies, one pass over at most 52 distinct letter buckets.
Space: O(1) — the frequency map holds at most 52 entries (a–z plus A–Z), a constant.

Complexity Summary

Common Mistakes

• Adding 1 for every odd-count character instead of at most once — only one character can sit at the center; the check length < len(s) correctly fires at most once regardless of how many characters have odd counts.
• Forgetting to add the center +1 at all — after collecting pairs, if any character had an odd count the result without the +1 is the longest even-length palindrome, which misses a longer odd-length one.
• Confusing this with Longest Palindromic Substring — that problem asks for the longest contiguous palindrome already embedded in s, not the longest palindrome you can construct by rearranging characters.
• Ignoring case sensitivity — 'A' and 'a' are different characters; they must be counted separately. Lowercasing the input before counting will give wrong answers.
• Computing the actual palindrome string — the problem only asks for the length; constructing the string wastes time and is not required.

Related Problems

• Palindromic Substrings — counts every palindromic substring already present in the string, using expand-around-center rather than frequency counting
• Longest Palindromic Substring — finds the longest palindromic contiguous substring; requires DP or expand-around-center, not just character counts
• Valid Palindrome — checks whether a string already is a palindrome after filtering non-alphanumeric characters
• Palindrome Number — determines if an integer reads the same forwards and backwards without converting it to a string
• Palindrome Partitioning — uses backtracking to split a string into the maximum number of palindromic substrings