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<>();
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.
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.