Longest Palindromic Subsequence
Maintained by Vikas D, 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.
Examples
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.
Constraints
- 1 <= s.length <= 1000
- s consists only of lowercase English letters
- The answer is always at least 1 for any non-empty input
Visible test cases
- longestPalindromicSubsequence("bbbab") == 4
- longestPalindromicSubsequence("cbbd") == 2
- longestPalindromicSubsequence("a") == 1
- longestPalindromicSubsequence("abcba") == 5
- longestPalindromicSubsequence("abcd") == 1
Hints
Hint 1
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].
Hint 2
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.
Hint 3
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.
Approaches
Brute force over subsequences
Time O(n * 2^n) · Space O(n)Generate every subsequence and check which ones are palindromes, tracking the longest. This directly mirrors the definition but explores an exponential search space.
- Enumerate all 2^n subsequences of s, for example with a bitmask over the n positions
- For each subsequence, test whether it equals its reverse
- Track the maximum length seen among the palindromic ones
- Return that maximum (a single character guarantees at least 1)
Interval DP, then space-optimized
Time O(n^2) · Space O(n)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).
- Let dp[i][j] be the LPS length of s[i..j]; set every dp[i][i] to 1
- Iterate i from n-1 down to 0 and j from i+1 up to n-1 so inner windows are ready
- If s[i] equals s[j], dp[i][j] = dp[i+1][j-1] + 2; otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1])
- Replace the full table with a prev and curr row (curr[i]=1 each pass, swap after each i) to use only O(n) space
- Return dp[0][n-1], which after the rolling reduction is prev[n-1]
Common mistakes
- Confusing subsequence with substring. Substring requires contiguous characters; here gaps are allowed, so a sliding-window or contiguous-expansion approach gives the wrong, smaller answer.
- Filling the dp table in the wrong order. dp[i][j] needs dp[i+1][...] and dp[i][j-1] already computed, so i must descend and j must ascend; iterating i upward reads cells that are still zero.
- Forgetting the base case dp[i][i] = 1, which makes single characters and the diagonal contribute nothing and undercounts every result.
- When space-optimizing, mishandling the dp[i+1][j-1] term. After moving to two rows you must read the previous row's j-1 entry before it gets overwritten, which the i-descending, j-ascending order preserves.
Follow-up variations
- Reconstruct and return one actual longest palindromic subsequence, not just its length, by backtracking through the dp table.
- Solve the related problem of the minimum number of insertions to make the whole string a palindrome (it equals n minus the LPS length).
- Handle a very long string where O(n^2) time is too slow, and discuss what bounds are achievable for general strings.
- Count how many distinct longest palindromic subsequences exist, not just the length of one.