5.js

/** ------------------------------------------------------------------------------
 * 
 * 5. Longest Palindromic Substring
 * Topics: Two Pointers, DP
 * https://leetcode.com/problems/longest-palindromic-substring/?envType=problem-list-v2&envId=two-pointers
 * 
 ------------------------------------------------------------------------------ */
var longestPalindrome = function (s) {
  if (!s) return ""
  let start = 0
  let end = 0

  for (let i = 0; i < s.length; i++) {
    const odd = expandCenter(s, i, i)
    const even = expandCenter(s, i, i + 1)

    if (even > end - start) {
      start = i - (odd - 1) / 2
      end = i + even / 2
    }

    if (odd > end - start) {
      start = i - (odd - 1) / 2
      end = i + odd / 2
    }
  }

  return s.slice(start, end + 1)
}

const expandCenter = (s, left, right) => {
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    left--
    right++
  }

  return right - left - 1
}

var longestPalindrome = function (s) {
  const len = s.length

  let longestPalLength = 0
  let longestPalLeft = 0
  let longestPalRight = 0

  const getLongestPalindrome = (leftPosition, rightPosition) => {
    while (leftPosition >= 0 && rightPosition < len && s[leftPosition] === s[rightPosition]) {
      leftPosition--
      rightPosition++
    }

    if (rightPosition - leftPosition > longestPalLength) {
      longestPalLeft = leftPosition + 1
      longestPalRight = rightPosition - 1
      longestPalLength = longestPalRight - longestPalLeft + 1
    }
  }

  // Loop through the letters
  for (let i = 0; i < len; i++) {
    getLongestPalindrome(i, i + 1)
    getLongestPalindrome(i, i)

    if ((len - i) * 2 < longestPalLength) {
      // Break out to avoid unnecessary computation
      break
    }
  }

  return string.slice(longestPalLeft, longestPalRight + 1)
}

/**
 * DP
 */
var longestPalindrome = function (s) {
  const n = s.length
  if (n === 0) return ""

  const dp = new Array(n).fill().map(() => new Array(n).fill(false))

  for (let i = 0; i < n; i++) {
    dp[i][i] = true
  }

  let maxLen = 1
  let start = 0
  for (let i = 0; i < n - 1; i++) {
    if (s[i] === s[i + 1]) {
      dp[i][i + 1] = true
      start = i
      maxLen = 2
    }
  }

  for (let len = 3; len <= n; len++) {
    for (let i = 0; i < n - len + 1; i++) {
      const j = i + len - 1
      if (dp[i + 1][j - 1] && s[i] === s[j]) {
        dp[i][j] = true
        if (len > maxLen) {
          maxLen = len
          start = i
        }
      }
    }
  }
  return s.slice(start, start + maxLen)
}

// 2D DP
var longestPalindrome = function (s) {
  if (s.length <= 1) return s

  const dp = [...new Array(s.length + 1)].map((_) => new Array(s.length + 1).fill(false))

  let lps = ""
  for (let i = 0; i < s.length; i++) {
    dp[i][i] = true
    lps = s[i]
  }

  console.log(dp)

  for (let i = 0; i < s.length; i++) {
    if (s[i] === s[i + 1]) dp[i][i + 1] = true
    if (dp[i][i + 1]) lps = s.substring(i, i + 2)
  }

  // expand to three or more characters
  for (let i = s.length - 1; i >= 0; i--) {
    for (let j = i + 2; j < s.length; j++) {
      dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j]
      if (dp[i][j]) lps = lps.length < j - i + 1 ? s.substring(i, j + 1) : lps
    }
  }

  return lps
}