Skip to main content
Back to ChallengesLongest Palindromic SubsequenceHard 30 min

Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence's length in s.

Examples

Input: s = 'bbbab'
Output: 4
One possible longest palindromic subsequence is 'bbbb'.
Input: s = 'cbbd'
Output: 2
LPS is 'bb', length 2.

Constraints

  • • 1 <= s.length <= 1000
  • • s consists of lowercase English letters.

Complexity Analysis

Time
O(n^2)
interval DP matrix scan.
Space
O(n^2)
matrix storing results for indices [i...j].

Test Cases

#1 LPS of 4
Input: "bbbab"
Expected: 4
#2 LPS of 2
Input: "cbbd"
Expected: 2
Output
Click "Run Code" to see output here...