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

Length of longest palindrome that can be built from a string

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.

.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
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 {
}
}
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.