DEV Community

Duncan McArdle
Duncan McArdle

Posted on

2

LeetCode problem #5 — Longest Palindromic Substring (JavaScript)

In this LeetCode challenge we’re asked to find the longest palindrome in a given string (a palindrome being a sequence of characters that is the same backwards as it is forwards, such as “bob”).

Now you might be inclined to think that the solution to this is simply to look at every character, and then move outwards until the characters no longer mirror each other. However, whilst this would work for a string like “aba”, it would not work for a string like “abba”, so we need to look for mirrored characters both by individual letter, and by letter-couple.

Solution #1: Loop, call twice, and store globally

Not a catchy title I know, but as this is my only real solution a catchy name seemed unnecessary!

In this solution, we loop through all characters in the string, and for each one, we begin checking for palindromes both on the current character and on the current character-couple. For each palindrome found, we check if it’s the new longest one, and store it if so.

var longestPalindrome = function (string) {
let longestPal = '';
var getLongestPalindrome = function (leftPosition, rightPosition) {
// While there is space to expand, and the expanded strings match
while (
leftPosition >= 0 &&
rightPosition < string.length &&
string[leftPosition] === string[rightPosition]
) {
// Expand in each direction.
leftPosition--;
rightPosition++;
}
// Store the longest palindrom (if it's the longest one found so far)
if (rightPosition - leftPosition > longestPal.length) {
longestPal = string.slice(leftPosition + 1, rightPosition);
}
};
// Loop through the letters
for (let i = 0; i < string.length; i++) {
// Find the longest odd palendrome
getLongestPalindrome(i, i + 1);
// Find the longest even palendrome
getLongestPalindrome(i, i);
// Check if a longer palindrome cannot be found
if ((string.length - i) * 2 < longestPal.length) {
// Break out to avoid unnecessary computation
break;
}
}
return longestPal;
};

This solution works great, and is pretty quick. In fact, the only way I’ve found to improve its performance is to replace the somewhat expensive string storing operations with pointer storage instead. In other words, instead of storing (and subsequently overwriting) the longest palindromes found each time, we instead store (and overwrite) pointers to the start and end of the longest palindrome. As you can imagine, once we get seriously long strings, this really starts to improve performance (at the cost of readability).

var longestPalindrome = function (string) {
let longestPalLength = 0;
let longestPalLeft = 0;
let longestPalRight = 0;
var getLongestPalindrome = function (leftPosition, rightPosition) {
// While there is space to expand, and the expanded strings match
while (
leftPosition >= 0 &&
rightPosition < string.length &&
string[leftPosition] === string[rightPosition]
) {
//expand in each direction.
leftPosition--;
rightPosition++;
}
// Store the longest palindrome (if it's the longest one found so far)
if (rightPosition - leftPosition > longestPalLength) {
longestPalLeft = leftPosition + 1;
longestPalRight = rightPosition - 1;
longestPalLength = longestPalRight - longestPalLeft + 1;
}
};
// Loop through the letters
for (let i = 0; i < string.length; i++) {
// Find the longest odd palendrome
getLongestPalindrome(i, i + 1);
// Find the longest even palendrome
getLongestPalindrome(i, i);
// Check if a longer palindrome cannot be found
if ((string.length - i) * 2 < longestPalLength) {
// Break out to avoid unnecessary computation
break;
}
}
return string.slice(longestPalLeft, longestPalRight + 1);
};

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more

Top comments (1)

Collapse
 
256hz profile image
Abe Dolinger

really like this solution, thanks for writing it up!

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs