LeetCode-in-All

5. Longest Palindromic Substring

Medium

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = “babad”

Output: “bab” Note: “aba” is also a valid answer.

Example 2:

Input: s = “cbbd”

Output: “bb”

Example 3:

Input: s = “a”

Output: “a”

Example 4:

Input: s = “ac”

Output: “a”

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Solution

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    const newStr = new Array(s.length * 2 + 1).fill('#')
    for (let i = 0; i < s.length; i++) {
        newStr[2 * i + 1] = s[i]
    }

    const dp = new Array(newStr.length).fill(0)
    let friendCenter = 0
    let friendRadius = 0
    let lpsCenter = 0
    let lpsRadius = 0

    for (let i = 0; i < newStr.length; i++) {
        dp[i] =
            friendCenter + friendRadius > i ? Math.min(dp[2 * friendCenter - i], friendCenter + friendRadius - i) : 1

        while (i + dp[i] < newStr.length && i - dp[i] >= 0 && newStr[i + dp[i]] === newStr[i - dp[i]]) {
            dp[i]++
        }

        if (friendCenter + friendRadius < i + dp[i]) {
            friendCenter = i
            friendRadius = dp[i]
        }

        if (lpsRadius < dp[i]) {
            lpsCenter = i
            lpsRadius = dp[i]
        }
    }

    const start = Math.floor((lpsCenter - lpsRadius + 1) / 2)
    const end = Math.floor((lpsCenter + lpsRadius - 1) / 2)
    return s.substring(start, end)
}

export { longestPalindrome }

This site is open source. Improve this page.