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.