Longest Palindromic Subsequence
Longest Palindromic Subsequence: return the length of the longest subsequence of s that reads the same forwards and backwards. Characters may be dropped but not reordered.
- 1 <= s.length <= 1000
- s consists only of lowercase English letters
Intuition
Look at the two ends of a range. If they match, both belong to some longest palindrome and contribute 2 on top of the answer for the interior. If they differ, at least one must be discarded, so take the better of dropping the left end or the right end. That recurrence is defined on ranges rather than prefixes, which is what makes this an interval DP filled by increasing length.
A DP indexed by a range rather than a prefix is the signal for interval DP, and the tell is a recurrence that peels from both ends. Longest Palindromic Substring, Palindromic Substrings, and Minimum Insertion Steps to Make a String Palindrome share the structure.
Approach
Before reading on: write the recurrence for a range whose two ends match, and for one where they differ. Then work out which order the table must be filled in so that every dependency is already computed.
The recurrence on ranges, and why the ends decide it
Let dp[i][j] be the answer for the substring s[i..j]. When s[i] == s[j], pairing them is never a loss: any palindrome inside s[i+1..j-1] can be wrapped by that matching pair, so dp[i][j] = dp[i+1][j-1] + 2. When they differ, no palindrome can use both ends, so one must go, giving dp[i][j] = max(dp[i+1][j], dp[i][j-1]). The base case is a single character, dp[i][i] = 1, since one character is a palindrome of length 1.
Filling order: by length, not by index
Every entry depends on strictly shorter ranges — dp[i+1][j-1], dp[i+1][j], and dp[i][j-1] all span fewer characters than dp[i][j]. So the table must be filled in increasing order of range length, or equivalently with i descending and j ascending. A naive nested loop with both indices ascending reads entries that have not been computed yet and silently returns wrong answers rather than crashing, which makes the ordering the single most important detail here.
Cost, and the relationship to LCS
The table has O(n²) entries and each is filled in constant time, so the algorithm is O(n²) time and O(n²) space; keeping only two rows reduces the space to O(n). There is a well-known equivalence: the longest palindromic subsequence of s equals the longest common subsequence of s and its reverse, because a subsequence appearing in both is exactly one that reads the same either way. That route is easier to remember but does the same asymptotic work with a larger constant.
Solution & live demo
Common pitfalls
Filling the table with both indices ascending
for i in range(n):
for j in range(i + 1, n):for i in range(n - 1, -1, -1):
for j in range(i + 1, n):dp[i][j] depends on dp[i+1][...], which belongs to a later row. Filling i upward reads zeros from uncomputed entries, so the answer is silently too small rather than an error.
Adding 2 without the interior term
dp[i][j] = 2
dp[i][j] = dp[i + 1][j - 1] + 2
The matching ends wrap whatever palindrome lies between them. Discarding the interior result reports only the outermost pair and loses everything nested inside.
Solving for substrings instead of subsequences
requiring the characters to be contiguous
allow characters to be skipped
A subsequence may drop characters freely. Treating it as a substring answers a different question — for "bbbab" it gives 3 instead of the correct 4.
Edge cases
The base case gives 1 directly with no recurrence applied.
Every pair of ends matches and the answer equals the length.
No pair matches, so the answer is 1.
Every range matches at both ends and the answer is the full length.
The max branch picks either single character, giving 1.