Home Strings Length of longest palindrome that can be built from a string

Length of longest palindrome that can be built from a string

by nikoo28
1 comment

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

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.

1 comment

You may also like

1 comment

Longest Palindromic Substring – Study Algorithms – Strings October 10, 2020 - 05:44

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

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

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

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More