Longest Palindromic Subsequence
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.

30:00

Longest Palindromic Subsequence
medium
Topics
Companies

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: "bbbab"
Output: 4
Constraints:

  • 1≤s.length≤10001 \leq s.\text{length} \leq 1000

  • s consists only of lowercase English letters.

Input
arr ="bbbab"

Initialize DP table

b
b
b
a
b
DP Table (dp[i][j] = LPS length for s[i..j])
b
b
b
a
b
b
0
0
0
0
0
b
-
0
0
0
0
b
-
-
0
0
0
a
-
-
-
0
0
b
-
-
-
-
0
Variables
No variables to display
DepthFunction Call
Stack empty
0/12