[leetcode] 5. Longest Palindromic Substring

Table of Contents

Description

Given a string s, return the longest palindromic substring in 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.

Approach

Assuming each element is the center point of a palindromic string, calculate the longest palindromic substring that can be generated for both odd and even lengths.

Solution

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let longestPalindromeString = "";

  for (let i = 0; i < s.length; i++) {
    // Find the longest odd-length palindrome centered at i
    oddLongestPalindromeString = expandAroundCenter(s, i, i);
    if (oddLongestPalindromeString.length > longestPalindromeString.length)
      longestPalindromeString = oddLongestPalindromeString;

    // Find the longest even-length palindrome centered between i and i+1
    evenLongestPalindromeString = expandAroundCenter(s, i, i + 1);
    if (evenLongestPalindromeString.length > longestPalindromeString.length)
      longestPalindromeString = evenLongestPalindromeString;
  }

  return longestPalindromeString;
};

function expandAroundCenter(s, left, right) {
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    left--;
    right++;
  }
  // Return the palindromic substring found by slicing from left+1 to right
  return s.slice(left + 1, right);
}

Complexity Analysis

Time Complexity

The time complexity for this solution is O(n^2) because we expand around the center for each element in the string s.

Space Complexity

The space complexity is O(1) because we only use a few variables to store the longest palindromic substring.