Introduction to Palindromic Subsequence Pattern

You are given a string. Find the length of its longest palindromic subsequence, meaning the longest set of characters that reads the same both ways when the others are removed.

"cddpd"   the answer is 3, from "d d d"
"pqr"     the answer is 1, since no two characters match

Checking every subsequence is exact and hopeless. A string of length n has 2^n subsequences.

Look at the two ends instead. For any stretch of the string, exactly one of two things is true.

• The characters at the two ends match