LeetCode 5 · Medium · 1-D Dynamic Programming

Longest Palindromic Substring

Given a string s, return its longest contiguous piece that reads the same forward and backward.

O(n²)time
O(1)space
expandaround 2n−1 centres

letters and digits · 1–16 characters

public String longestPalindrome(String s) { String res = ""; int resLen = 0, n = s.length(); for (int i = 0; i < n; i++) { // odd length int l = i, r = i; while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) { if (r - l + 1 > resLen) { res = s.substring(l, r + 1); resLen = r - l + 1; } l--; r++; } // even length l = i; r = i + 1; while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) { if (r - l + 1 > resLen) { res = s.substring(l, r + 1); resLen = r - l + 1; } l--; r++; } } return res;}
i
—
l, r
—
resLen
0
res
""

Why it works

  1. Brute force checks every substring: O(n²) substrings, each checked in O(n), so O(n³).
  2. Grow from the middle: a palindrome stays a palindrome when you peel off its two ends. So start at a centre and step l left and r right while the two new characters match. The first mismatch ends every longer palindrome with that centre.
  3. Every centre, twice: odd lengths centre on a character, even lengths between two. That is 2n − 1 centres, each expanding at most n/2 times: O(n²) time, and only a few indices of space.
  4. Pitfall: forgetting the even case. "cbbd" has no odd palindrome longer than 1, but "bb" sits between indices 1 and 2.
  5. Track the best span as you go: compare r − l + 1 with resLen on every match, so the answer needs no second pass.
  6. Follow-ups: a 2-D dp table dp[l][r] = s.charAt(l) == s.charAt(r) && dp[l + 1][r − 1] is also O(n²) but uses O(n²) space. Manacher's algorithm reaches O(n). Palindromic Substrings counts every match instead of keeping the longest.