005. Longest Palindromic Substring

At a Glance

Topic: Two Pointers
Pattern: Analyze Pattern
Difficulty: Medium
LeetCode: 005

Problem Statement

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 & Solution Steps

Brute force — check every substring — O(n^3) time.
Better — 2D DP: isPalindrome[left][right] — O(n^2) time / O(n^2) space.
Optimal (interview) — expand from each center — O(n^2) time / O(1) space. <- pick this in interview.
Optimal (DP shown) — bottom-up table — O(n^2) time / O(n^2) space for learning.

Optimal JS Solution

function longestPalindromeTable(s) {
  const length = s.length;
  if (length <= 1) return s;
  const table = Array.from({ length }, () => new Array(length).fill(false));
  let bestStart = 0;
  let bestLength = 1;
  for (let end = 0; end < length; end++) {
    table[end][end] = true;
    for (let start = 0; start < end; start++) {
      if (
        s[start] === s[end] &&
        (end - start < 2 || table[start + 1][end - 1])
      ) {
        table[start][end] = true;
        if (end - start + 1 > bestLength) {
          bestLength = end - start + 1;
          bestStart = start;
        }
      }
    }
  }
  return s.slice(bestStart, bestStart + bestLength);
}

function longestPalindrome(s) {
  const length = s.length;
  if (length <= 1) return s;
  let bestStart = 0;
  let bestLength = 1;
  const expand = (left, right) => {
    while (left >= 0 && right < length && s[left] === s[right]) {
      const currentLength = right - left + 1;
      if (currentLength > bestLength) {
        bestLength = currentLength;
        bestStart = left;
      }
      left--;
      right++;
    }
  };
  for (let center = 0; center < length; center++) {
    expand(center, center);
    expand(center, center + 1);
  }
  return s.slice(bestStart, bestStart + bestLength);
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.