Arrays & Hashing · 170Easy
Longest Palindrome
Given a string s of lowercase and uppercase letters, return the length of the longest palindrome that can be BUILT from those letters (each letter used at most as many times as it appears). Letters are case sensitive: "Aa" is not a palindrome.
Constraints
- 1 <= s.length <= 2000
- s consists of lowercase and/or uppercase English letters only.
Examples
longestPalindrome("abccccdd") -> 7 // e.g. "dccaccd"
longestPalindrome("a") -> 1 // single letter
longestPalindrome("Aa") -> 1 // case sensitive — no pair here
longestPalindrome("bb") -> 2 // one clean pair
longestPalindrome("abc") -> 1 // no pairs; one odd letter sits in the middle
longestPalindrome("abccba") -> 6 // already a palindromeEdge cases
- A letter with an odd count still contributes count - 1 letters.
- At most ONE odd-count letter can sit in the middle.
Show the target complexity (spoiler)
- Naive
- Trying arrangements is exponential; there is no reason to.
- Target
- O(n) time, O(1) space (52 letters) — count letters, add every even part, and add 1 if any count was odd.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/01-arrays-hashing/170-longest-palindrome.js ./practice c 170