# Length of longest palindrome that can be built from a string

By | April 30, 2018

Question: Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

Input: “abccccdd”

Output: 7

In the above example, the longest palindrome in the given string is “dccaccd” whose length is 7.

A palindrome consists of letters with equal partners, plus possibly a unique center (without a partner). The letter i from the left has its partner i from the right. For example in ‘abcba’, ‘aa’ and ‘bb’ are partners, and ‘c’ is a unique center.

Imagine we built our palindrome. It consists of as many partnered letters as possible, plus a unique center if possible. This motivates a greedy approach.

Algorithm:
We use a HashSet to find the number of partnered characters. Since we are only interested in the length of the longest palindrome possible, we can then have the result.

```public int longestPalindrome(String s) {

if(s==null || s.length()==0)
return 0;

HashSet<Character> hs = new HashSet<Character>();
int count = 0;

for(int i = 0; i < s.length(); i++) {
if(hs.contains(s.charAt(i))) {
hs.remove(s.charAt(i));
count++;
} else {
}
}
if(!hs.isEmpty())
return count * 2 + 1;

return count * 2;
}
```

A working solution can be found at:- https://ideone.com/8CNFQG

Time Complexity: O(N), where N is the length of s. We need to count each letter.
Space Complexity: O(1), the space for our count, as the alphabet size of s is fixed.
We should also consider that in a bit complexity model, technically we need O(log N) bits to store the count values.

Author: nikoo28

a tech-savvy guy and a design buff...

This site uses Akismet to reduce spam. Learn how your comment data is processed.