DEV Community is a community of 665,273 amazing developers

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

LeetCode 409. Longest Palindrome (javascript solution)

codingpineapple

Description:

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

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

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

``````// "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."
var longestPalindrome = function(s) {
let longest = 0;
let keys = {};

for (const char of s) {
// Keep track of character count in the keys object
keys[char] = (keys[char] || 0) + 1;
// If add 2 to the longest variable everytime we hit an even number count
if (keys[char] % 2 == 0) longest += 2;
}
// If s.length is greater than longest then we know that we can add a unique char in the middle of the palindrome
return s.length > longest ? longest + 1 : longest;
};
``````