Maintained by Vikas Dulgunde, software engineer
You are given a string s. A subsequence is what you get by removing zero or more characters while keeping the rest in their original order, so it does not have to be contiguous. A string is a palindrome when it is identical to its own reverse.
Your job is to return the length of the longest subsequence of s that is a palindrome. You only need the length, not the subsequence itself, and you never rearrange characters.
Every single character counts as a palindrome of length 1, so the answer is at least 1 for any non-empty input. When characters repeat in mirrored positions, you can pair them up around a center to grow the palindrome.
Note this is the subsequence version, not the substring version. Because gaps are allowed, the answer can be much larger than the longest contiguous palindrome, which makes the matching far more flexible.
Dropping the 'a' leaves "bbbb", a palindrome of length 4. No length-5 palindromic subsequence exists because the single 'a' cannot be mirrored.
The two adjacent b's form "bb". The 'c' and 'd' each appear once and cannot pair with anything, so 2 is the best.
Every character is distinct, so no two positions mirror each other. Any single letter is a length-1 palindrome and that is the maximum.
The whole string already reads the same in reverse, so the entire string is the longest palindromic subsequence.
Visible test cases
Look at the outermost characters of a window. If s[i] equals s[j], those two can sit on the ends of a palindrome, so they add 2 to whatever the best answer is for the inside window s[i+1..j-1].
If the two ends differ, at least one of them is not part of the answer for this window, so try dropping the left end and dropping the right end and keep the larger result.
Define dp[i][j] as the longest palindromic subsequence within s[i..j]. Build it by interval length, with every single character giving dp[i][i] = 1, and you only need to fill the upper triangle where i <= j.
Generate every subsequence and check which ones are palindromes, tracking the longest. This directly mirrors the definition but explores an exponential search space.
An LPS over s[i..j] is built from smaller windows: matching ends contribute 2 plus the inner answer, mismatched ends take the better of dropping one side. Filling a 2D table by interval gives O(n^2), and because each row depends only on the previous one, two rolling 1D arrays cut space to O(n).