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<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 { 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.