hardDynamic Programming 2DPure DSA~30 min
Longest Palindromic Subsequence
Find the length of the longest subsequence of a string that reads the same forwards and backwards (characters need not be contiguous).
Problem
Given a string s, return the length of the longest palindromic subsequence in s.
Input
A string s of lowercase letters.
Output
An integer: the length of the longest palindromic subsequence.
Constraints
- 1 <= s.length <= 1000
- s consists of lowercase English letters.
- The subsequence need not be contiguous.
Examples
Example 1
Input
s = "bbbab"
Output
4
'bbbb' is the longest palindromic subsequence.
Example 2
Input
s = "cbbd"
Output
2
'bb' has length 2.