Longest Palindromic Subsequence

Medium20–25 min

Topics

Dynamic ProgrammingString

Companies

AmazonGoogleAdobe

Given a string s, find the length of the longest subsequence of it that reads the same forwards and backwards — the characters don't need to be contiguous, just in the same relative order. The two ends of the string decide everything at each step: if they're equal, both can anchor the palindrome and the problem shrinks to the interval strictly between them, plus 2; if they differ, at least one end has to be left out, so the best answer is whichever of "drop the left end" or "drop the right end" works out better. That's exactly the recurrence for the longest common subsequence between s and its own reverse — but expressing it directly as an interval DP over (i, j) pairs of the same string avoids building a second string entirely, and it's the shape that generalizes cleanly to interval-DP problems beyond palindromes.

Test Case 1:

Input:s = "bbbab"

Output:4

Explanation:Dropping just the middle "a" leaves "bbbb" — four characters, in order, reading the same forwards and backwards.

Test Case 2:

Input:s = "cbbd"

Output:2

Explanation:No 3+ character subsequence here reads the same both ways, but the two b's together do — "bb".

Test Case 3:

Input:s = ""

Output:0

Explanation:An empty string has no characters to form a palindrome from, so the answer is 0.

Constraints

◆0 ≤ s.length ≤ 12
◆s consists of lowercase English letters only

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Interval Shrinking

Brute

Look at the string through its two end characters. If they match, they can both be part of the palindrome, and what's left to decide is the best palindromic subsequence strictly between them — so add 2 and recurse on the inner interval. If they don't match, at least one of them can't be part of the answer, so try dropping the left end and try dropping the right end, and keep whichever recursive result is longer. Repeating this choice at every interval explores every possible subsequence, but the same (i, j) intervals get revisited across many different call paths, since nothing is cached.

TimeO(2ⁿ)

SpaceO(n)

Java

Try it out

class Solution {
    public int longestPalindromeSubseq(String s) {
        return solve(s, 0, s.length() - 1);
    }
    private int solve(String s, int i, int j) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (s.charAt(i) == s.charAt(j)) {
            return 2 + solve(s, i + 1, j - 1);
        }
        return Math.max(solve(s, i + 1, j), solve(s, i, j - 1));
    }
}

Optimal — Bottom-Up Interval DP

Optimal

Cache the same recursion in a table instead of recomputing it: dp[i][j] holds the longest palindromic subsequence length within s[i..j]. Every single character is trivially a palindrome of length 1, which fills the diagonal. Then build up by increasing interval length — for each (i, j), if the end characters match, dp[i][j] = dp[i+1][j-1] + 2 (or just 1 when i+1 > j-1, i.e. the interval has length 2); otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Because every wider interval only depends on strictly shorter ones already computed, filling by increasing length guarantees everything needed is ready. The final answer sits at dp[0][n-1].

TimeO(n²)

SpaceO(n²)