Longest Palindromic Subsequence

Given a string s, return the length of the longest subsequence of s that is also a palindrome. Pattern focus: Longest palindromic subsequence. This is the canonical 2D DP palindromic subsequence problem.

Input Format

s = input string

Output Format

length of the longest palindromic subsequence

Constraints

  • 0 <= s.length <= 1000
  • s contains lowercase English letters.

Examples

Example 1:

Input:

s = "bbbab"

Output:

4

Explanation:

One longest palindromic subsequence is bbbb.

Example 2:

Input:

s = "cbbd"

Output:

2

Explanation:

The subsequence bb is the longest palindrome.

Loading...
Longest Palindromic Subsequence - Dp Strings