Longest Palindromic Substring

Loading...LeetCode

Given a string s, return the longest

palindromicsubstringin s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000

• s consist of only digits and English letters.

You can solve this problem using dynamic programming combined with expanding around the center technique in JavaScript. Here's a possible implementation:

function longestPalindrome(s) {
    if (s.length < 1) return "";

    let start = 0;
    let end = 0;

    for (let i = 0; i < s.length; i++) {
        const len1 = expandAroundCenter(s, i, i);
        const len2 = expandAroundCenter(s, i, i + 1);
        const len = Math.max(len1, len2);

        if (len > end - start) {
            start = i - Math.floor((len - 1) / 2);
            end = i + Math.floor(len / 2);
        }
    }

    return s.substring(start, end + 1);
}

function expandAroundCenter(s, left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

// Test cases
console.log(longestPalindrome("babad")); // Output: "bab" or "aba"
console.log(longestPalindrome("cbbd"));  // Output: "bb"

In this implementation, the longestPalindrome function iterates through each character of the string s. For each character, it expands around the center (either single character or between two characters) to find the longest palindrome with that character as the center. The expandAroundCenter function is used for this purpose. Finally, it returns the longest palindrome found.