Longest Palindrome
Description
You get a string s of lowercase and uppercase letters. Return the length of the longest palindrome you can build with those letters, using each letter at most as many times as it appears.
Letters are case sensitive: "Aa" is not a palindrome.
Examples
Example 1
Input: s = "abccccdd"
Output: 7
Explanation: dccaccd is one longest palindrome: two d's, four c's, and one leftover letter, a, in the middle.
Example 2
Input: s = "a"
Output: 1
Explanation: A single letter is a palindrome of length 1.
Constraints
- 1 ≤ s.length ≤ 2000
- s consists of lowercase and/or uppercase English letters only.
Editorial
Brute Force
Intuition
A palindrome mirrors around its middle, and the letters can go in any order. So only the counts matter: each pair of a letter can sit on both sides, and at most one leftover letter can sit in the middle. The direct way counts each distinct letter with its own scan of the string.
Step-by-Step Explanation
Let's count s = "abccccdd":
- Scan for 'a': 1 copy. None pair up, so the length is 0.
- Scan for 'b': 1 copy. None pair up, so the length is 0.
- Scan for 'c': 4 copies. All 4 pair up, so the length is 4.
- Scan for 'd': 2 copies. Both pair up, so the length is 6.
- 4 scans of 8 letters, 32 reads. Pairs give 6. 'a' and 'b' are left over, and one leftover letter can sit in the middle, so the answer is 7.
One Scan per Letter — Each step scans the whole string for one letter; the copies it finds are indigo.
Algorithm
- For each distinct letter, scan
sto count it. - Add the count rounded down to even; remember whether any count was odd.
- Add 1 if some count was odd.
Code
class Solution {
public:
int longestPalindrome(string s) {
int length = 0;
bool hasOdd = false;
string seen;
for (char c : s) {
if (seen.find(c) != string::npos) continue; // each distinct letter once
seen += c;
int k = count(s.begin(), s.end(), c); // a full scan to count it
length += k - k % 2;
if (k % 2) hasOdd = true;
}
return length + (hasOdd ? 1 : 0);
}
};
class Solution:
def longestPalindrome(self, s: str) -> int:
length, has_odd = 0, False
for c in set(s): # each distinct letter once
k = s.count(c) # a full scan to count it
length += k - k % 2
has_odd = has_odd or k % 2 == 1
return length + (1 if has_odd else 0)
class Solution {
public int longestPalindrome(String s) {
int length = 0;
boolean hasOdd = false;
boolean[] done = new boolean[128];
for (char c : s.toCharArray()) {
if (done[c]) continue; // each distinct letter once
done[c] = true;
int k = 0;
for (char d : s.toCharArray()) if (d == c) k++; // a full scan to count it
length += k - k % 2;
if (k % 2 == 1) hasOdd = true;
}
return length + (hasOdd ? 1 : 0);
}
}
var longestPalindrome = function(s) {
let length = 0, hasOdd = false;
for (const c of new Set(s)) { // each distinct letter once
let k = 0;
for (const d of s) if (d === c) k++; // a full scan to count it
length += k - (k % 2);
if (k % 2) hasOdd = true;
}
return length + (hasOdd ? 1 : 0);
};
Complexity Analysis
Time Complexity: O(k · n)
One scan per distinct letter, up to 52 of them.
Space Complexity: O(k)
Why This Approach Is Not Efficient
It passes, but it reads the string once per distinct letter: up to 52 times. One pass with a count for every letter gets all the counts at once.
Optimal Approach - Count Once
Intuition
Count every letter in one pass, with an array of 128 slots indexed by the character's code, so 'A' and 'a' land in different slots. Then each count rounded down to even goes into the palindrome, and if any count was odd, one leftover letter goes in the middle.
Step-by-Step Explanation
Let's count s = "abccccdd":
- Count each letter in one pass. Every second copy of a letter completes a pair, and a pair adds 2.
- The first 'a' waits for a partner.
- The first 'b' waits for a partner.
- The first 'c' waits for a partner.
- The second 'c' completes a pair, so the length grows to 2.
- The third 'c' waits for a partner.
- The fourth 'c' completes a pair, so the length grows to 4.
- The first 'd' waits for a partner.
- The second 'd' completes a pair, so the length grows to 6.
- Pairs give 6. 'a' and 'b' are left over, and one leftover letter can sit in the middle, so the answer is 7.
Count the Pairs — Green letters have found a partner. Indigo letters are still waiting for one.
Algorithm
- Count each character in an array of 128.
- Sum
k - k % 2over the counts. - Add 1 if any count is odd.
Code
class Solution {
public:
int longestPalindrome(string s) {
int counts[128] = {0}; // one slot per ASCII code: 'A' and 'a' are different letters
for (char c : s) counts[(unsigned char)c]++;
int length = 0;
bool hasOdd = false;
for (int k : counts) {
length += k - k % 2; // every pair of a letter can mirror around the middle
if (k % 2) hasOdd = true;
}
return length + (hasOdd ? 1 : 0); // one leftover letter can sit in the middle
}
};
class Solution:
def longestPalindrome(self, s: str) -> int:
counts = [0] * 128 # one slot per ASCII code: 'A' and 'a' are different letters
for c in s:
counts[ord(c)] += 1
length = sum(k - k % 2 for k in counts) # every pair of a letter can mirror around the middle
has_odd = any(k % 2 for k in counts)
return length + (1 if has_odd else 0) # one leftover letter can sit in the middle
class Solution {
public int longestPalindrome(String s) {
int[] counts = new int[128]; // one slot per ASCII code: 'A' and 'a' are different letters
for (char c : s.toCharArray()) counts[c]++;
int length = 0;
boolean hasOdd = false;
for (int k : counts) {
length += k - k % 2; // every pair of a letter can mirror around the middle
if (k % 2 == 1) hasOdd = true;
}
return length + (hasOdd ? 1 : 0); // one leftover letter can sit in the middle
}
}
var longestPalindrome = function(s) {
const counts = new Array(128).fill(0); // one slot per ASCII code: 'A' and 'a' are different letters
for (let i = 0; i < s.length; i++) counts[s.charCodeAt(i)]++;
let length = 0, hasOdd = false;
for (const k of counts) {
length += k - (k % 2); // every pair of a letter can mirror around the middle
if (k % 2) hasOdd = true;
}
return length + (hasOdd ? 1 : 0); // one leftover letter can sit in the middle
};
Complexity Analysis
Time Complexity: O(n)
One pass, then 128 counts.
Space Complexity: O(1)
128 counts, whatever the length.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Adding one for every odd count. + sum(k % 2 for k in counts.values())
On s = "abccccdd" it returns 8; the answer is 7. Only one letter can sit alone in the middle. Every other odd count gives up its extra letter.
Dropping odd counts whole. sum(k for k in counts.values() if k % 2 == 0)
On s = "aaabb" it returns 3; the answer is 5. A letter that appears 3 times still has a pair to give: its count minus one goes in, and only the extra letter is in question.
Ignoring case. for c in s.lower():
On s = "Aa" it returns 2; the answer is 1. Letters are case sensitive: 'A' and 'a' can't mirror each other. Count them apart.
Forgetting the middle letter. return sum(k - k % 2 for k in counts.values())
On s = "abccccdd" it returns 6; the answer is 7. When any count is odd, one leftover letter can sit in the middle: add 1.
Where This Pattern Is Taught
Counting letters with an array is taught in Introduction to Strings, and palindromes in Palindromes: Expand Around the Center, which shows how this problem differs from finding palindromic substrings.