Longest Palindrome
Last Updated: March 29, 2026
Understanding the Problem
We're not asked to find a palindrome within the string. We're asked to build the longest possible palindrome using the characters available in the string. We can rearrange characters however we want, and we don't have to use all of them.
What makes a string a palindrome? It reads the same forwards and backwards. That means every character must appear in pairs, one for each side. The only exception is the middle character: if the palindrome has an odd length, exactly one character can appear an odd number of times (it sits in the center).
So the real question is: how many characters can we use? Every character that appears an even number of times can be fully used. For characters that appear an odd number of times, we can use all but one of them (the even portion), and then place one leftover character in the middle. That observation is the entire solution.
Key Constraints:
1 <= s.length <= 2000→ With n up to 2000, even O(n^2) would run in about 4 million operations, well within limits. But this problem doesn't need anything beyond O(n).sconsists of lowercase and/or uppercase English letters only → At most 52 distinct characters (26 lowercase + 26 uppercase). This means our frequency map has a fixed, small size.
Approach 1: Brute Force (Check All Subsequences)
Intuition
The most direct interpretation: try every possible subset of the string's characters, check if each subset can form a palindrome, and return the length of the longest one. A subset of characters can form a palindrome if at most one character has an odd frequency.
This is wildly impractical, but it helps frame why we need a smarter approach.
Algorithm
- Generate all possible subsequences of the string (there are 2^n of them).
- For each subsequence, count character frequencies.
- Check if at most one character has an odd frequency (palindrome condition).
- Track the maximum length among all valid subsequences.
Code
- Time Complexity: O(2^n * n). There are 2^n subsets, and for each one we iterate through the string to build the frequency map. With n up to 2000, this is astronomically infeasible.
- Space Complexity: O(1). The frequency array has a fixed size of 128 (ASCII), so it's constant space.
This approach is conceptually straightforward but exponential in time. We don't actually need to enumerate subsets. The palindrome structure tells us exactly how many characters we can use from the frequency counts alone.
Approach 2: Greedy with Hash Map
Intuition
Here's the key insight that makes this problem easy: you don't need to build the palindrome. You just need to figure out how many characters you can use.
A palindrome has a mirror structure. Every character on the left half has a matching character on the right half. So any character that appears an even number of times can be fully used, all copies go into the palindrome. A character that appears an odd number of times? You can use count - 1 copies (the largest even number less than count), and that one leftover can potentially go in the center.
But there's only one center position. So at most one "leftover" character can be placed in the middle. After summing up all the even contributions, if there was at least one character with an odd count, we add 1 for the center.
The palindrome structure dictates exactly which characters are usable. Characters pair up symmetrically around the center, so only even quantities contribute to the two halves. The count / 2 * 2 formula extracts the even portion of any count (for odd counts like 5, it gives 4; for even counts like 4, it gives 4). The hasOdd flag handles the center position: if any character had leftovers, one of them can sit in the middle.
This is a greedy approach because we're making the locally optimal choice for each character (use as many as possible) and it leads to the globally optimal answer.
Algorithm
- Count the frequency of each character in the string using a hash map.
- Initialize
length = 0andhasOdd = false. - For each character frequency:
- Add
freq / 2 * 2tolength(the largest even number <= freq). This is the even portion. - If
freqis odd, sethasOdd = true. - If
hasOddis true, add 1 tolength(for the center character). - Return
length.
Example Walkthrough
Code
- Time Complexity: O(n). One pass through the string to build the frequency map, then one pass through the frequency array (size 128, constant). Total is O(n).
- Space Complexity: O(1). The frequency array has a fixed size of 128 regardless of input size. If we used a hash map, it would hold at most 52 entries (26 lowercase + 26 uppercase), which is still constant.
This approach counts everything first, then processes. Can we determine the palindrome length in a single pass without building a full frequency map?
Approach 3: Optimal (Single Pass with Set)
Intuition
Instead of counting frequencies and then analyzing them, we can use a set to track characters with odd counts as we go. When we see a character, if it's already in the set (meaning we've seen it an odd number of times), we remove it and add 2 to our length (we just completed a pair). If it's not in the set, we add it (marking that we've seen it an odd number of times so far).
At the end, if the set is non-empty, there's at least one character with an odd count, so we can add 1 for the center.
The set acts as a parity tracker. A character enters the set when we've seen it an odd number of times and leaves when we've seen it an even number of times. Every time a character leaves, we've found a complete pair, so we add 2. At the end, the set contains exactly the characters with odd frequencies, and any one of them can serve as the center of the palindrome.
This is mathematically equivalent to Approach 2. The frequency-based approach says: take the even portion of each count, then add 1 if any odd count exists. The set-based approach counts pairs as they form, then checks for leftovers. Same logic, different bookkeeping.
Algorithm
- Initialize an empty set and
length = 0. - Iterate through each character in the string:
- If the character is already in the set, remove it and add 2 to
length(a pair is formed). - Otherwise, add the character to the set.
- If the set is non-empty after the loop, add 1 to
length(center character). - Return
length.
Example Walkthrough
Code
- Time Complexity: O(n). Single pass through the string. Each character involves one O(1) set operation (lookup + insert or remove).
- Space Complexity: O(1). The set holds at most 52 characters (the size of the alphabet). This is constant regardless of input size.