Longest palindromic subsequence - DSA Practice

Given a string, Find the longest palindromic subsequence length in given string.

A palindrome is a sequence that reads the same backwards as forward.

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 = "eeeme"

Output: 4

Explanation: The longest palindromic subsequence is "eeee", which has a length of 4.

Example 2:

Input: s = "annb"

Output: 2

Explanation: The longest palindromic subsequence is "nn", which has a length of 2.

Now Your Turn!

Pick the correct output for the given input

Input: s = "s"

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

1 ≤ s.length ≤ 1000

148. Longest palindromic subsequence

Example 1:

Example 2:

Now Your Turn!

Constraints:

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

Example 1:

Example 2:

Now Your Turn!

Constraints:

Hints

Hint 1

Frequently Occurring Doubts

Why does this problem resemble the Longest Common Subsequence (LCS)?

Why do we take max(dp[i+1][j], dp[i][j-1]) when s[i] ≠ s[j]?

Interview Follow-up Questions

How would you reconstruct the actual longest palindromic subsequence instead of just its length?

What if we wanted the shortest sequence that becomes a palindrome after insertions?

Fun Facts

Fun Fact 1

Fun Fact 2