Medium

Quiz

#516 Longest Palindromic Subsequence

APPROACH

Given a string s, determine the length of the longest subsequence within s that reads the same forwards and backwards. A subsequence is obtained by removing any characters from s without disturbing the relative order of the remaining characters.

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".

1 of 4

1:00

What is the optimal approach for this problem?