Longest Palindrome
The key idea
A palindrome mirrors around its center. Every letter that appears an even number of times can be split symmetrically across both halves. From an odd count you can still use all but one of its copies (the largest even number below it). If any letter had an odd count, exactly one leftover copy can sit alone in the middle, adding 1.
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.
You do not build the palindrome itself; you only return how long the longest possible one is, using each available letter at most as many times as it appears in s.
Constraints
1 <= s.length <= 2000sconsists of lowercase and/or uppercase English letters only.
Examples
Input: s = "abccccdd"
Output: 7
Input: s = "a"
Output: 1
Input: s = "bb"
Output: 2
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Majority Element IIMEDIUM