Medium · Dynamic Programming

Longest Palindromic Subsequence

Given a string s, return the length of its longest palindromic subsequence: the longest sequence of its characters, kept in their original order but not necessarily adjacent, that reads the same forwards and backwards.

Examples

Example 1

s = "bbbab"

Output: LPS = 4

Example 2

s = "cbbd"

Output: LPS = 2

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.

More Dynamic Programming problems