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

Core interview problems are free with a full runner and lessons; Pro opens the complete library.

More Dynamic Programming problems