#409 Longest Palindrome

frequently reported atGoogle Amazon Microsoft

the problem

In plain words

Given a string of uppercase and lowercase English letters, return the length of the longest palindrome you can build by rearranging some (or all) of its letters. Letters are case-sensitive: "Aa" is not a palindrome.

in s = "abccccdd"

out 7

For example "dccaccd": two d's, four c's, and one a in the middle.

in s = "a"

out 1

1 ≤ s.length ≤ 2000
Uppercase and lowercase English letters only

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternFrequency counting

A palindrome is mirrored pairs around a centre. Use every pair you can; if any letter has a copy left over, exactly one of them can sit in the middle.

solutions

From brute force to optimal

Sorting puts equal letters together; each run contributes its even part.

Sort the chars.
For each run of length r: add r / 2 * 2; note if r is odd.
Add 1 if any run was odd.

timeO(n log n)

The sort dominates.

spaceO(n)

toCharArray makes a copy.

javajava.util.*

1class Solution {2    public int longestPalindrome(String s) {3        char[] c = s.toCharArray();4        Arrays.sort(c);                                   // equal letters become one run5        int length = 0;6        boolean anyOdd = false;7        for (int i = 0; i < c.length; ) {8            int j = i;9            while (j < c.length && c[j] == c[i]) j++;     // run c[i..j-1]10            int run = j - i;11            length += run / 2 * 2;                         // use every pair12            if (run % 2 == 1) anyOdd = true;13            i = j;14        }15        return anyOdd ? length + 1 : length;               // one leftover letter fits in the middle16    }17}

A letter waits in the set until its partner arrives; then the pair is counted and the letter leaves.

For each c: if waiting.remove(c) succeeds, pairs++; else waiting.add(c).
Answer = pairs × 2, + 1 if anyone is still waiting.

timeO(n)

One O(1)-average set operation per letter.

spaceO(1)

At most 52 letters wait at once.

javajava.util.*

1class Solution {2    public int longestPalindrome(String s) {3        Set<Character> waiting = new HashSet<>();          // letters still looking for a partner4        int pairs = 0;5        for (char c : s.toCharArray()) {6            if (!waiting.remove(c)) waiting.add(c);        // remove() true → a pair is complete7            else pairs++;8        }9        return pairs * 2 + (waiting.isEmpty() ? 0 : 1);10    }11}

Count every letter by its ASCII code, take the even part of each count, and add one centre if anything is left over.

count[c]++ for every char.
length = Σ count / 2 * 2.
If length < s.length(), add 1.

timeO(n)

One pass to count plus 128 slots to sum.

spaceO(1)

128 counters, whatever the input size.

javajava.util.*

1class Solution {2    public int longestPalindrome(String s) {3        int[] count = new int[128];                        // 'A'..'Z' and 'a'..'z' are ASCII4        for (int i = 0; i < s.length(); i++) count[s.charAt(i)]++;5        int length = 0;6        for (int c : count) length += c / 2 * 2;           // the even part of every count7        return length < s.length() ? length + 1 : length;  // something was left over → one centre8    }9}

in the room

How to say it in the interview

talk track

Say what a palindrome needs: every letter an even number of times, except at most one in the centre.
Ask about case: the problem is case-sensitive, so 'A' and 'a' are different letters — that's why int[128], not int[26] with c − 'a'.

traps

Adding 1 for every odd count instead of once — only one letter can be the centre.
Dropping odd counts entirely: 5 copies still give 4 letters (two pairs).
int[26] with c - 'a': uppercase letters give negative indices.

what they ask next

Follow-ups

Build the actual palindrome string?

Write half of each pair on the left, mirror it on the right, and put one leftover letter in the middle.

Longest palindromic substring (LC 5)?

A different problem: letters can't be rearranged, so you expand around each centre — see the Dynamic Programming chapter.

before you submit

Edge cases to test

One letter → 1.
Case matters: "Aa" → 1.
All counts odd ("abc" → 1, "ccc" → 3).
Everything pairs up ("bb" → 2): no centre to add.

practise next