5. Longest Palindromic Substring

At a Glance

Topic: dp-1d
Pattern: Dynamic Programming and/or expand around center; Two Pointers for expand
Difficulty: Medium
Companies: Amazon, Google, Meta, Bloomberg, Microsoft
Frequency: Very High
LeetCode: 5

Problem (one-liner)

Given a string s, return any contiguous substring of s that is a palindrome and has maximum possible length. Input: string. Output: longest palindromic substring (any one if multiple).

Recognition Cues

“Longest palindromic substring” (contiguous)
Brute force is O(n^3); expand or table gets O(n^2) or better for manacher (not required here)
All length-1 substrings are palindromes

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

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 Solution

Go

package main

func longestPalindromeTable(s string) string {
	length := len(s)
	if length <= 1 {
		return s
	}
	table := make([][]bool, length)
	for index := range table {
		table[index] = make([]bool, length)
	}
	bestStart := 0
	bestLength := 1
	for end := 0; end < length; end++ {
		table[end][end] = true
		for 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[bestStart : bestStart+bestLength]
}

func longestPalindrome(s string) string {
	length := len(s)
	if length <= 1 {
		return s
	}
	bestStart := 0
	bestLength := 1
	expand := func(left int, right int) {
		for left >= 0 && right < length && s[left] == s[right] {
			currentLength := right - left + 1
			if currentLength > bestLength {
				bestLength = currentLength
				bestStart = left
			}
			left--
			right++
		}
	}
	for center := 0; center < length; center++ {
		expand(center, center)
		expand(center, center+1)
	}
	return s[bestStart : bestStart+bestLength]
}

JavaScript

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);
}