#409
Longest Palindrome
Easy Frequency count
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Using the letters of s (case-sensitive), return the length of the longest palindrome you can build.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: using these letters, how long a palindrome can you build?
Why this works: pairs go on both sides; one leftover odd letter can sit in the middle.
Example: "abccccdd"
c4 → 4, d2 → 2, a1 b1 → odd6 + 1 = 7 ("dccaccd")
✦Hints open one at a time
Letters used in pairs can go on both sides.
One letter with an odd count can sit in the middle.
↗Approach
Count each character. Add count / 2 * 2 for every character, and add 1 at the end if any count was odd.
</>Solution (Java)
class Solution {
public int longestPalindrome(String s) {
int[] count = new int[128];
for (char c : s.toCharArray()) count[c]++;
int len = 0;
boolean odd = false;
for (int c : count) {
len += c / 2 * 2; // pairs
if (c % 2 == 1) odd = true;
}
return odd ? len + 1 : len;
}
}!Common mistake
Adding every odd count fully — only one odd letter can be in the middle.
Complexity
- Time: O(n).
- Space: O(charset).
Topic: Strings
🎬 Episodes 16–20: video coming soon