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;
}
```

Code language: Java (java)

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.

## 2 comments

You are given a set of riddles. Each riddle will be in the form of a long string of jumbled alphabets (all the alphabets will be lowercase). As an answer to the riddle, you have to tell the length of the longest possible palindrome that can be formed from the given alphabet sequence. Note that the alphabets can be arranged in any sequence to form the palindrome.

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

Comments are closed.