Longest Palindrome — Solution in Python, Java & C++
Longest Palindrome solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Longest Palindrome is an easy coding problem on strings, hash table and greedy, asked in Amazon, Google and Bloomberg interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table, Greedy
- Asked at: Amazon, Google, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s of upper and lowercase letters, return the length of the longest palindrome that can be built using those letters, in any order. Case matters: "Aa" is not a pair.
Example 1
Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome is "dccaccd".
Example 2
Input: s = "a"
Output: 1
Example 3
Input: s = "bb"
Output: 2
Constraints
1 <= s.length <= 40s consists of upper and lowercase English letters.
Hints for Longest Palindrome
Hint 1
A palindrome uses every letter an even number of times, except possibly one letter in the exact middle.
Hint 2
So take the largest even number below or equal to each letter's count.
Hint 3
If any letter had an odd count, one leftover can still sit in the centre — add 1.
How to solve Longest Palindrome
Pairs of equal letters can be mirrored around the centre; take the even part of every count, and add one more if any count was odd to occupy the middle.
Approach
- Count every character.
- Sum
count - (count % 2)over all characters. - If any count is odd, add 1.
Why it works
A palindrome uses each letter an even number of times except at most one letter in the exact centre. Taking the largest even number ≤ each count uses the maximum pairs, and a single odd leftover fills the centre.
Complexity
- Time —
O(n) - Space —
O(1) — 52 possible letters
Pitfalls
- Case-sensitive:
Aandado not pair. - Add the centre once, not once per odd count.
Reference solution
Python
def longestPalindrome(s: str) -> int:
count = {}
for ch in s:
count[ch] = count.get(ch, 0) + 1
total = 0
has_odd = False
for c in count.values():
total += c - (c % 2)
if c % 2 == 1:
has_odd = True
return total + (1 if has_odd else 0)Java
public static int longestPalindrome(String s) {
int[] count = new int[128];
for (int i = 0; i < s.length(); i++) count[s.charAt(i)]++;
int total = 0;
boolean hasOdd = false;
for (int c : count) {
total += c - (c % 2);
if (c % 2 == 1) hasOdd = true;
}
return total + (hasOdd ? 1 : 0);
}C++
int longestPalindrome(string s) {
int count[128] = {0};
for (char ch : s) count[(int) ch]++;
int total = 0;
bool hasOdd = false;
for (int i = 0; i < 128; i++) {
total += count[i] - (count[i] % 2);
if (count[i] % 2 == 1) hasOdd = true;
}
return total + (hasOdd ? 1 : 0);
}JavaScript
var longestPalindrome = function(s) {
const count = new Map();
for (let i = 0; i < s.length; i++) {
count.set(s[i], (count.get(s[i]) || 0) + 1);
}
let total = 0, hasOdd = false;
count.forEach(function(c) {
total += c - (c % 2);
if (c % 2 === 1) hasOdd = true;
});
return total + (hasOdd ? 1 : 0);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets