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
2 comments 3 minutes read

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.

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))) {
        } else {
        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.

You may also like


orangakpqrs October 8, 2021 - 01:55

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.

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

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

Comments are closed.

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