Reduction
LPS(S) = LCS(S, reverse(S)). O(N²) DP inherited.
Advertisement
Direct DP
dp[i][j] = LPS of S[i..j]. If S[i]==S[j]: dp[i+1][j-1] + 2. Else max(dp[i+1][j], dp[i][j-1]).
Advertisement
vs Longest palindromic substring
Substring = contiguous. Subsequence = not necessarily. Different algorithms.
Space
O(N²) DP → O(N) with rolling arrays. Reconstruct with O(N²) memory.