Question:Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromesthat 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<>();
int count = 0;
for(int i = 0; i < s.length(); i++) {
if(hs.contains(s.charAt(i))) {
hs.remove(s.charAt(i));
count++;
} else {
hs.add(s.charAt(i));
}
}
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.

*O(1), the space for our count, as the alphabet size of s is fixed.*

**Space Complexity:**We should also consider that in a bit complexity model, technically we need O(log N) bits to store the count values.

## 1 comment

[…] Length of longest palindrome that can be built from a string […]