Longest Palindrome You Can Build from a String

01 · Strip it down

Rearrange freely, report the longest palindrome's length

Given a string of upper- and lowercase letters, you may reorder the characters however you like. Return the maximum length of a palindrome you could build — you never need to print the palindrome itself. For bbde (b:2, d:1, e:1), use the pair bb and drop one odd letter in the middle: bdb, length 3.

The structural fact that decides everything A palindrome is symmetric: every character off-center must appear in a matching pair, and at most one leftover character can sit in the center.

02 · The reframe

Rearrangement allowed → count, don't construct

Because order is yours to choose, bbde, edbb, and bdeb all give the same answer — only the frequencies matter. That kills the tempting brute forces: generating permutations is O(N!), trying every subset is O(2ᴺ), and both solve a harder problem than asked. You just need pair arithmetic.

Don't confuse it with longest palindromic substring That problem forbids rearrangement and needs a contiguous palindrome (expand-around-center / DP / Manacher). Here you rebuild from loose letters — completely different, and far simpler. Always check first: is rearrangement allowed?

03 · From frequency to length

Take every complete pair, then maybe one center

For a character appearing f times, the most you can use symmetrically is the largest even number ≤ f, i.e. (f / 2) * 2. Sum those across all characters. Then, if any character had an odd count, one leftover can take the single center seat — add 1.

Even frequency

use all of it

f = 4 → 4 f = 6 → 6. Fully pairable.

Odd frequency

use f − 1

f = 5 → 4 f = 1 → 0. One copy left over.

Only one leftover ever counts With a:3, b:3, c:3 you can't use all 9 — a palindrome has exactly one center. You get 2+2+2 + 1 = 7, not 9. Extra odd leftovers are simply discarded.

Matching socks

You can only wear socks in pairs. Count how many complete pairs each color makes; odd ones leave a single sock behind — and you're allowed to display just one lone sock, in the middle.

A mirror down the middle

Whatever you place on the left must be reflected on the right. Only the letter sitting exactly on the mirror line escapes needing a twin.

Splitting a resource budget

Each letter is a stock of parts. Every symmetric slot costs 2 identical parts. Spend as many full pairs as you can afford, then treat yourself to one single-part centerpiece.

04 · Build one

Count, split into pairs, assemble

Type a string (or pick one). Each letter's count splits into pair blocks and a possible leftover. The stage assembles an actual palindrome: pairs mirror across the dashed center line, and one leftover (if any) drops into the middle in blue.

Palindrome builder

length: 0

Try aaabbbccc (three odds → only one center used), AaBb (case matters, all singletons → length 1), or aabbcc (all even → use everything).

05 · Two things people get wrong

Case matters, and one odd count is fine

Uppercase ≠ lowercase

"Aa" → 1

A and a are different characters — no pair. Never lowercase-normalize; an int[128] keeps them in separate slots automatically.

One odd is allowed

abcba is valid

Only even-length palindromes need all-even counts. An odd-length one permits exactly one odd-frequency character at the center.

06 · The code

Count, sum pairs, add a center

static int longestPalindrome(String s) {
    int[] freq = new int[128];        // covers A-Z and a-z separately
    for (char ch : s.toCharArray()) freq[ch]++;

    int length = 0;
    boolean hasOdd = false;
    for (int c : freq) {
        length += (c / 2) * 2;             // largest even ≤ c
        if (c % 2 == 1) hasOdd = true;
    }
    if (hasOdd) length++;                  // one center seat
    return length;
}

Counting is O(N); scanning the fixed 128-slot table is constant. So it's O(N) time, O(1) space — optimal, since you must read every character once. An equivalent one-liner formula: with oddCount odd-frequency letters, the answer is s.length() − oddCount + 1 when any odd exists, else s.length(). The pair-based version is easier to reconstruct from first principles.

07 · Dry run

A few inputs, worked through

Input	Frequencies	Pairs used	Center?	Answer
`bbde`	b:2, d:1, e:1	2	+1	3
`aabbcc`	a:2, b:2, c:2	6	—	6
`abcd`	all 1	0	+1	1
`aaabbbccc`	a:3, b:3, c:3	6	+1	7
`AaBb`	A,a,B,b : 1	0	+1	1

The answer isn't just an upper bound — it's constructible. Lay each used pair symmetrically (aabc … cbaa) and slot one leftover between the halves; that string is automatically a palindrome.

08 · The pattern

Same tool, a different question

This is the third distinct question answered by frequency counting in this set. The tool is identical; what changes is the condition you read off the counts:

First unique element

global counts

condition: frequency == 1

Anagram windows

window vs pattern counts

condition: counts equal

Longest palindrome

global counts

condition: pairs + one leftover

The lesson

ask "what does a count buy me?"

not "which problem uses a HashMap?"

09 · One month from now

Reconstruct it, don't memorize it

I may rearrange, so order is irrelevant — only counts matter.
A palindrome is symmetric: off-center characters need pairs.
From each count, take as many full pairs as possible — that's (f/2)·2.
Sum the pairs.
If any count was odd, one leftover can sit in the center — add 1.

The transferable insight When rearrangement is allowed, stop reasoning about positions and start reasoning about available resources. The palindrome imposes a resource rule — two copies per mirrored slot, one optional center — so "build every palindrome" collapses into "count how many pairs you can afford."