DEV Community

codingpineapple
codingpineapple

Posted on

4 2

LeetCode 409. Longest Palindrome (javascript solution)

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;
};
Enter fullscreen mode Exit fullscreen mode

Heroku

Deliver your unique apps, your own way.

Heroku tackles the toil — patching and upgrading, 24/7 ops and security, build systems, failovers, and more. Stay focused on building great data-driven applications.

Learn More

Top comments (1)

Collapse
 
yashgada profile image
yashgada

Good one

Neon image

Next.js applications: Set up a Neon project in seconds

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Get started →

👋 Kindness is contagious

Engage with a wealth of insights in this thoughtful article, valued within the supportive DEV Community. Coders of every background are welcome to join in and add to our collective wisdom.

A sincere "thank you" often brightens someone’s day. Share your gratitude in the comments below!

On DEV, the act of sharing knowledge eases our journey and fortifies our community ties. Found value in this? A quick thank you to the author can make a significant impact.

Okay