Skip to main content

409. Longest Palindrome

easy

Given a string, return the length of the longest palindrome you can build by reusing its letters in any order. The whole problem collapses to one counting trick: pairs contribute fully, leftover odd counts contribute one shared center.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters. Letters are case sensitive, for example 'Aa' is not considered a palindrome.

Constraints

  • 1 <= s.length <= 2000
  • s consists of lowercase and/or uppercase English letters only.

Examples

Example 1

Input
s = 'abccccdd'
Output
7

Explanation: One longest palindrome is 'dccaccd' of length 7.

Example 2

Input
s = 'a'
Output
1

Example 3

Input
s = 'bb'
Output
2

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

A palindrome reads the same forward and backward, so most characters must appear in matched pairs. The center is optional.

Hint 2

Count each letter's frequency. Every even count contributes its full value. Every odd count contributes count - 1 paired letters.

Hint 3

If any letter has an odd count, you can place exactly one of them in the center, so add 1 to the result.

Solution approach

Reveal approach

Running-frequency map. Build a hash of character -> count in one pass over s. For each count, add (count // 2) * 2 to the total — this captures all pairs and drops at most one from each odd count. Track whether any odd count exists; if so, the palindrome can host a single center character, so add 1 at the end. The hash itself is the entire algorithm — no two pointers, no DP, no reordering of s needed because we're building the longest palindrome, not finding a substring.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • hash-map
  • counting
  • running-frequency-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta

Practice these live with InterviewChamp.AI

Drill Longest Palindrome and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →