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

Open every published interview problem, solution, scene, and memory room free, with no account.

More Dynamic Programming problems