Example 1
Input
bbbab
Output
4
One longest palindromic subsequence is 'bbbb', which has length 4.
Full lesson preview
Find the longest palindromic subsequence
Compute the length of the longest subsequence of a string that reads the same forwards and backwards using dynamic programming.
Python practice30 minDynamic ProgrammingAdvancedLast updated March 29, 2026
Problem statement
Given a string s, return the length of the longest palindromic subsequence in s. A subsequence is a sequence that can be derived from the string by deleting some or no characters without changing the order of the remaining characters. The subsequence does not need to be contiguous. You must design an algorithm using dynamic programming that runs in O(n^2) time and uses O(n^2) space in the worst case.
Task
Implement an efficient dynamic programming solution (O(n^2) time, O(n^2) space) to find the length of the longest palindromic subsequence in a given string.
Examples
Input format
A single string s.
Output format
An integer representing the length of the longest palindromic subsequence in s.
Constraints
0 <= len(s) <= 1000. s contains only printable ASCII characters. Expected time: O(n^2). Expected space: O(n^2) (can be optimized to O(n) with different approaches but not required here).
Samples
Sample 1
Input
agbdba
Output
5
A longest palindromic subsequence is 'abdba' of length 5.