Longest Palindromic Substring
Find the longest palindromic substring in a string.
Pattern fit
This problem is a good DP example because whether s[i..j] is a palindrome depends on a smaller interior substring plus the current boundary characters.
Key observation
A substring is a palindrome if its endpoints match and the inner substring is also a palindrome, with short substrings handled as base cases.
Target complexity
O(n^2) / O(n^2)
How to break down the solution cleanly
This problem is a good DP example because whether s[i..j] is a palindrome depends on a smaller interior substring plus the current boundary characters.
A substring is a palindrome if its endpoints match and the inner substring is also a palindrome, with short substrings handled as base cases.
Name the state in plain language.
List the decisions that can transition into the state.
Reference implementation
Python# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = transition(dp, i)
# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = transition(dp, i, j)
Common pitfalls
Iterating in the wrong order so dp[i+1][j-1] is not ready.
Forgetting that length 1 and 2 substrings need special initialization.
Common follow-ups
What is the center-expansion alternative?
How would you reduce space if only the answer length mattered?
Continue with related problems
Build repeatable depth inside the Dynamic Programming cluster before moving on.