Longest Palindrome

You are handed a string s made of English letters. Treat its characters as a bag of tiles: you may use each tile at most once and arrange the chosen tiles in any order you like.

Return the length of the longest palindrome (a string that reads the same forwards and backwards) you can build from those tiles. You do not have to use every tile.

Letters are case-sensitive, so "B" and "b" are different tiles and cannot mirror each other.

Example 1

Example 2

Example 3

Constraints

• 1 <= s.length <= 2 * 104
• s contains only lowercase and uppercase English letters.

Pattern Path · Hashing & Counting · problem 4 of 169

Start simple

Generating arrangements of subsets and testing each for being a palindrome is exponential; the counting approach needs only O(n).

The key idea

Since we may rearrange freely, only the count of each letter matters. A palindrome is built from mirrored pairs: whatever appears at position i from the left also appears at position i from the right. So a letter that occurs c times can contribute c // 2 pairs, i.e. c - c % 2 characters.

There is one exception to the pairing rule: the single middle position of an odd-length palindrome has no partner. If any letter had an odd count, one of its leftover copies can occupy that spot, adding 1 to the length. Only one such bonus is allowed, no matter how many letters are odd.

So: count the letters, add up the even parts, and add 1 if at least one count was odd. This is greedy and provably optimal: no palindrome can use more than the even part of any letter outside the center, and the center holds at most one character.

Complexity

• Time: O(n)
• Space: O(1) (at most 52 distinct letters)

Python

from collections import Counter


class Solution:
    def longestPalindrome(self, s: str) -> int:
        counts = Counter(s)
        length = 0
        has_odd = False
        for c in counts.values():
            length += c - c % 2      # use the largest even number of copies
            if c % 2 == 1:
                has_odd = True
        # one leftover character may sit in the middle
        return length + 1 if has_odd else length

JavaScript

var longestPalindrome = function(s) {
  const counts = new Map();
  for (const ch of s) counts.set(ch, (counts.get(ch) || 0) + 1);
  let length = 0;
  let hasOdd = false;
  for (const c of counts.values()) {
    length += c - (c % 2);   // use the largest even number of copies
    if (c % 2 === 1) hasOdd = true;
  }
  // one leftover character may sit in the middle
  return hasOdd ? length + 1 : length;
};

What the interviewer is checking

The interviewer wants to see you reduce the problem to letter counts and reason about the structure of a palindrome instead of trying to construct one.

Mistakes to avoid

• Adding 1 for every letter with an odd count instead of at most once overall.
• Throwing away all copies of an odd-count letter: a letter seen 5 times still contributes 4.
• Treating uppercase and lowercase as the same letter.

Follow-ups to expect

• Can you return an actual palindrome of that length? (Build half, mirror it, add a center.)
• Can you do it in a single pass? (Track odd letters in a set.)
• What if the alphabet were arbitrary Unicode? (Hash map still works, O(k) space.)

In real software

Answering "can these parts be arranged symmetrically?" by counting rather than searching shows up in inventory checks, pairing problems and quick feasibility filters before an expensive search.

Practice next