Longest Palindromic Subsequence

Standard Bar Dynamic Programming · DP on Strings O(n^2) · O(n^2)

The Ribbon Weave Symmetry

A textile archivist analyzes thread sequences from ancient ribbons, looking for the longest thread pattern that reads identically forwards and backwards after ignoring unrelated threads. The longer the preserved palindrome motif, the more valuable the ribbon's provenance. The catalog needs that motif length per specimen.

Input: A string s.

Output: Return the length of the longest subsequence of s that is a palindrome.

Constraints

1 <= len(s) <= 1000
s consists of lowercase English letters

Examples

Example 1

Input: {"s":"bbbab"}
Output: 4
Dropping the lone 'a' leaves "bbbb" — a length-4 palindrome.

Example 2

Input: {"s":"cbbd"}
Output: 2
"bb" is the best symmetric motif.

Solve this in your browser →

Also on LeetCode ↗