## DEV Community is a community of 696,672 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Leetcode Daily - Longest Palindrome Andrew Hsu
Software engineer with an electrical engineering background. Enjoys technical problem solving and working in a team.

# Leetcode Daily - August 14, 2020

## Longest Palindrome

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

## Question

(Copy Pasted From Leetcode)

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

``````Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
``````

## My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

### Attempt 1 - Determine Logical Conditions For Longest Palindrome Length

##### (Submission - Accepted)

I ended up approaching this as a logic problem instead of as a computer science problem. The first thing I noticed is that, except for a middle character, palindromes have matching pairs of the same character symmetric with the middle. So if we were to count how many of each unique character we have, all even sets would be able to go on a palindrome, but there is only space for only one odd "spare" letter.

I decided to pseudocode first and then write my code following this blueprint:

• Count each of the letters and store the counts

• Go through each of the counts and start adding them to a sum

• The sum is the length of the longest palindrome length
• If a count is even, we add it
• If the count is odd, and we haven't seen an odd, we add it
• If the count is odd, and we already added an odd, we add that count minus one (the largest even value we can add)

Submitted Code (Javascript):

``````var longestPalindrome = function(s) {
// palindrome can only contain up to one odd set of letters
// all even sets of letters work
// go through the string and store all the unique letter counts
const dict = {}

for (let i = 0; i < s.length; i++) {
if (dict[s[i]]) {
dict[s[i]] += 1
} else {
dict[s[i]] = 1
}
}

// make an array of our letter counts to iterate on
let letterCount = []
Object.keys(dict).forEach(key => {
letterCount.push(dict[key])
})

// create variables to remember how long our longest palindrome is
// as well as whether we have our one odd letter set
let sum = 0
let seenEven = false
// start adding up letter sets

for (let count of letterCount) {
if (count % 2 === 0) {
sum += count
} else {
if (!seenEven) {
// add odd set if haven't seen one yet
sum += count
seenEven = true
} else {
// turn into even set and add
sum += count - 1
}
}
}
return sum
};
``````

## Discussion and Conclusions

I think the solution based on logic is very straightforward, and has time and space complexity of O(n) where n is the length of s. There are probably programming and computer science tricks that can optimize this code even further.

For example, I thought about it afterwards and instead of storing whether we have seen an odd or not, we could always add the "evenized" value, for example `count - (count%2)`. Then add the end, if the longest palindrome length sum were less than s.length, we could simply add 1 (there are spare letters left).

Resubmitted Code:

``````var longestPalindrome = function(s) {
// palindrome can only contain up to one odd set of letters
// all even sets of letters work
// go through the string and store all the unique letter counts
const dict = {}

for (let i = 0; i < s.length; i++) {
if (dict[s[i]]) {
dict[s[i]] += 1
} else {
dict[s[i]] = 1
}
}

// make an array of our letter counts to iterate on
let letterCount = []
Object.keys(dict).forEach(key => {
letterCount.push(dict[key])
})

// create variables to remember how long our longest palindrome is
// as well as whether we have our one odd letter set
let sum = 0

// start adding up letter sets
for (let count of letterCount) {
sum += count - (count%2)
}
if (sum < s.length) sum ++
return sum
};
``````

## Discussion (1) Vidit Sarkar

Thanks for sharing the problem and your solution. Here is my approach.

``````var longestPalindrome = function(s) {
/*
1. We only need the length of the longest palindrome.
2. Store all character with its corresponding count in dict.
3. All characaters that appears even number of times will be part
of palindrome, so add their count to all_even_count.
4. Palindrome can contain only one character that occurs odd
number of time. So for the size to be maximum get the odd character
that appears max number of times and store it's occurence count in max_odd_count.
5. Return (all_even_count + max_odd_count).
*/
const dict = {}

for (let i = 0; i < s.length; i++) {
if (dict[s[i]]) {
dict[s[i]] += 1
} else {
dict[s[i]] = 1
}
}

let all_even_count = 0, max_odd_count = 0

for(var key in dict) {
if(dict[key]%2 === 0) {
all_even_count += dict[key]
} else {
max_odd_count = Math.max(max_odd_count, dict[key])
}
}

return all_even_count + max_odd_count;
};

``````