DSA problem
Longest Palindromic Subsequence
Given a string s, find the longest palindromic subsequence's length in s. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
A palindromic subsequence is one that reads the same forward and backward. Unlike a substring, the characters need not be contiguous — they only need to preserve their relative order in the original string. This subtle difference makes the problem amenable to a clean interval dynamic programming formulation.
A trick that exposes the structure: the answer equals the length of the longest common subsequence (LCS) of s and its reverse. That works but is overkill. The direct interval DP is faster to reason about and avoids constructing a second string.
The optimal approach defines dp[i][j] as the length of the longest palindromic subsequence in the substring s[i..j] (inclusive). The base case is dp[i][i] = 1. The recurrence is dp[i][j] = dp[i+1][j-1] + 2 when s[i] == s[j], otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Iterate by interval length from 2 to n. The final answer is dp[0][n-1], computed in O(n^2) time and O(n^2) space (compressible to O(n) with care).
Examples
s = "bbbab"4s = "cbbd"2s = "a"1Constraints
- 1 <= s.length <= 1000
- s consists only of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.