Why does only one odd letter count fully?

A palindrome mirrors around its centre, so every letter except the middle one needs a partner on the other side. From each letter you can use count // 2 pairs. Only one position, the middle, can hold a letter without a partner, so at most one leftover is used no matter how many letters have odd counts.

Is this the same as Longest Palindromic Substring?

No. Here you may rearrange the letters and only the length is asked, so counting is enough. Longest Palindromic Substring keeps the order and asks for a contiguous piece, which needs expanding around centres or DP.

Are uppercase and lowercase letters the same?

No. LeetCode 409 is case sensitive: 'Aa' cannot form a palindrome longer than 1, because A and a are different letters.

Why is the space O(1)?

There are only 52 possible letters, so the count table has a fixed size no matter how long the string is.

Longest Palindrome

Find the length of the longest palindrome that can be built from a string's letters by counting them, using every pair and adding one middle letter.

EasySolve on LeetCode

Problem Understanding

Longest Palindrome (LeetCode 409): given a string s of uppercase and lowercase letters, return the length of the longest palindrome that can be built with those letters. You may use each letter at most as many times as it appears, in any order. Letters are case sensitive.

Examples: "abccccdd" → 7 (for example dccaccd); "a" → 1.

The Intuition: Pairs Go on Both Sides

Read a palindrome from both ends and the letters match in pairs. So the question is only how many pairs you can make.

Count the letters.
Every pair fits. A letter that appears 5 times gives 2 pairs, 4 letters.
One letter may stand alone in the middle. If any count was odd, add 1.

The counting is the same hash-map tally as Valid Anagram. If the order of the letters is fixed, the problem becomes Longest Palindromic Substring instead.

Interactive Walkthrough

EVERY PAIR + ONE MIDDLE

COUNT THE LETTERS

counts

Length

Odd seen

Answer

Count every letter of "abccccdd". Letters are case sensitive

s[0] = 'a': count it, now 1

Legend & Complexity

The letter being counted, or whose pairs are being added

A letter whose pairs are already in the palindrome

odd: one left over, so it could be the middle

Time

O(n)

Space

O(1)

First every letter is counted, then each count is turned into pairs. Letters with an odd count are marked "odd". Try Case: A and a never pair up.

Dry Run Table

Input: s = "abccccdd".

Letter	Count	Pairs used	Left over	Length so far
a	1	0	1	0
b	1	0	1	0
c	4	4	0	4
d	2	2	0	6

At least one letter has a leftover, so add 1 for the middle. Answer: 7, for example dccaccd.

The Solution Template

One counting pass, then one pass over the counts. The Java, C++ and C versions index an array of 128 by character code.

Longest Palindrome Code

1var longestPalindrome = function(s) {
2    const counts = new Map();
3    for (const ch of s) {
4        counts.set(ch, (counts.get(ch) || 0) + 1);
5    }
6    let length = 0;
7    let hasOdd = false;
8    for (const count of counts.values()) {
9        length += Math.floor(count / 2) * 2;
10        if (count % 2 === 1) {
11            hasOdd = true;
12        }
13    }
14    if (hasOdd) {
15        length += 1;
16    }
17    return length;
18};

Edge Cases & Common Mistakes

Single letter: no pairs, but it is a palindrome by itself, so the answer is 1.
All counts even: nothing is left over and the middle is not added.
Adding 1 for every odd letter: only one middle exists; odd letters still give their pairs, just not their leftovers.
Treating case as equal: 'A' and 'a' are different letters here.
Dropping odd counts entirely: a letter seen 3 times still gives one pair.

Summary

Count the letters, add count // 2 * 2 for each, and add 1 if any count was odd. O(n) time and O(1) space for the fixed letter set.

More practice: DSA interview questions with answers · patterns cheat sheet

Valid Anagram

Determine if Two Strings Are Close