Longest Palindrome
Compute the longest palindrome buildable from a multiset of letters using pair counting
Problem Statement
Given a string of lowercase and uppercase letters, return the length of the longest palindrome that can be built by rearranging its characters. Letters are case-sensitive: "Aa" is not a palindrome.
Input: "abccccdd"
Output: 7
Why: "dccaccd" (or similar) — uses cccc, dd, and one a
Input: "a"
Output: 1
Input: "bb"
Output: 2You do not have to build the palindrome
Only the length is required. That is what makes counting sufficient — the actual arrangement never has to be constructed.
Intuition
Think about the structure of a palindrome rather than about strings.
The key insight
A palindrome reads the same both ways, so every character must appear in a mirrored pair — one on the left, one on the right — with a single possible exception: one character may sit alone in the exact centre.
So the answer depends only on how many pairs you can form:
length = 2 × (total pairs) + (1 if any letter is left over, else 0)
Concretely: a letter appearing c times contributes c // 2 pairs, and leaves one spare if c is odd. All the spares are wasted except at most one, which becomes the centre.
Check it on "abccccdd":
a: 1 → 0 pairs, 1 left over
b: 1 → 0 pairs, 1 left over
c: 4 → 2 pairs, 0 left over
d: 2 → 1 pair, 0 left over
pairs = 3 → 6 characters
odd counts exist → +1 for the centre
answer = 7Real-world analogy
Building a symmetric wall from coloured bricks. Every brick you place on the left needs an identical one on the right, so bricks are useful only in pairs. A single odd brick can be placed at the exact centre — but only one, because the centre has room for just one.
Watch it run
Approach
Sum the pairs
Add count // 2 * 2 per letter — the number of characters usable in mirrored positions.
Add one if any count was odd
At most one leftover can be placed in the centre.
Solution
from collections import Counter
def longest_palindrome(s: str) -> int:
"""Length of the longest palindrome buildable from s's characters."""
counts = Counter(s)
length = 0
has_odd = False
for count in counts.values():
length += (count // 2) * 2 # only complete pairs are usable
if count % 2 == 1:
has_odd = True
return length + 1 if has_odd else lengthThe set-based version, which tracks parity instead of full counts:
def longest_palindrome_set(s: str) -> int:
unpaired: set[str] = set()
for char in s:
if char in unpaired:
unpaired.remove(char) # completed a pair
else:
unpaired.add(char)
# len(s) - len(unpaired) is the number of paired characters.
return len(s) - len(unpaired) + (1 if unpaired else 0)`(count // 2) * 2` is not the same as `count`
For count = 5 it gives 4, deliberately discarding the fifth character. Writing length += count would count every character including the unusable spares — the single most common mistake on this problem.
Case sensitivity
'A' and 'a' are different characters here. "Aa" has two letters with count 1 each, so the answer is 1, not 2. Lowercasing the input would be wrong.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(k)
- Time — one pass to count, one pass over the distinct letters.
- Space —
O(k)wherekis the alphabet size, at most 52 for mixed-case English letters — effectively constant.
Edge Cases
Related Problems
- Valid Palindrome — testing a palindrome rather than constructing one
- Valid Anagram — another problem reduced to character counts
- Number of Good Pairs — pair counting with the same
c × (c-1) / 2flavour of reasoning