LeetCode 5: Longest Palindromic Substring – JavaScript Solution

📌 Introduction

In this post, we'll solve LeetCode 5: Longest Palindromic Substring.
We'll cover the expand around centers approach and analyze the time and space complexities.
Code examples will be in JavaScript, with step-by-step explanations.

👉 Original problem link: LeetCode – Longest Palindromic Substring

---

1. Problem Overview

We need to find the longest palindromic substring within a given string. A palindrome reads the same forwards and backwards, like "racecar" or "aba". Our goal is to identify the longest such sequence of characters that exists as a contiguous substring in the input.

---

2. Example

Input: s = "babad"
Output: "bab"
Explanation: Both "bab" and "aba" are valid palindromes of length 3, making either a correct answer since they're both the longest possible.

Input: s = "cbbd"
Output: "bb"
Explanation: The characters "bb" form a palindrome of length 2, which is the longest palindromic substring in this case.

---

3. Approaches

🔹 Expand Around Centers Approach

Idea:

• Iterate through each character in the string

• For each position, try expanding outward to find palindromes

• Handle both odd-length palindromes (center on single character) and even-length palindromes (center between two characters)

• Track the longest palindrome found during expansion

• Return the maximum length palindromic substring

Code (JavaScript):

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    const n = s.length

    const expand = function(start, end){
        while(start >= 0 && end < n && s[start] == s[end]){
            start--
            end++
        }

        return s.substring(start + 1, end)
    }
    let max = ""
    for(let i = 0; i < n; i++){
        const evenString = expand(i, i+1)
        const oddString = expand(i, i)

        max = evenString.length > max.length ? evenString : max
        max = oddString.length > max.length ? oddString : max
    }

    return max
};

Time Complexity: O(N²)
Space Complexity: O(1)

---

4. Key Takeaways

• ✨ Expand around centers technique handles both odd and even length palindromes efficiently

• ✨ The helper function approach keeps the main logic clean and readable

• ✨ This solution trades some time complexity for simplicity compared to advanced algorithms like Manacher's algorithm