Problem Statement

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.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Problem Link

Longest Palindromic Subsequence - LeetCode

Approach

Length of Longest Palindromic Subsequence of string s = length of LCS(s,reverse(s)) 
                                                     

Complexity Analysis

Time and Space Complexity of the above implementation is O(mn)