Longest Palindrome
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 we can 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. The length follows directly from the character counts.
Key Constraints:
1 <= s.length <= 2000→ A single pass over the string is enough; the answer depends only on character counts, so an O(n) solution is the natural target.sconsists of lowercase and/or uppercase English letters only → At most 52 distinct characters (26 lowercase + 26 uppercase). The frequency map has a fixed, small size, which makes the per-character bookkeeping constant space.
Approach 1: Greedy with Hash Map
Intuition
We don't need to build the palindrome, only count how many characters can go into one.
A palindrome has a mirror structure: every character in the left half has a matching character in the right half. A character that appears an even number of times contributes all its copies. A character that appears an odd number of times contributes count - 1 copies (the largest even number below count), leaving one copy unused.
There is exactly one center position, so at most one unused copy can be placed in the middle. We sum the even contributions across all characters, then add 1 if any character had an odd count.
Integer division gives count / 2 * 2 as the largest even number not exceeding count (5 yields 4, 4 yields 4). Taking the even portion of every count is safe to do independently because pairs from different characters never compete: each pair occupies one symmetric slot on the left and its mirror on the right. The only shared resource is the single center slot, and the +1 claims it once if any odd count exists. No arrangement can do better, since the two halves must be identical multisets and that caps the usable count of each character at its even portion.
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 every character first, then processes the counts in a second pass over the frequency array. The next approach computes the same answer in a single pass over the string, tracking parity directly instead of storing full counts.
Approach 2: 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 the length (a pair is complete). 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 holds exactly the characters seen an odd number of times so far, since each occurrence toggles membership. A character toggles out on its even occurrences, and each toggle-out completes one pair and adds 2. After the loop, a character remains in the set precisely when its total count is odd, so the set size equals the number of odd-count characters. This matches Approach 1: the sum of pairs times 2 is the total even contribution, and a non-empty set is the same condition as hasOdd.
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.