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

Sentry blog image

How I fixed 20 seconds of lag for every user in just 20 minutes.

Our AI agent was running 10-20 seconds slower than it should, impacting both our own developers and our early adopters. See how I used Sentry Profiling to fix it in record time.

Read more

Top comments (1)

Collapse
 
yashgada profile image
yashgada

Good one

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay