LeetCode 409. Longest Palindrome (javascript solution)

#algorithms #javascript

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