Longest Palindromic Subsequence

MediumString DP · Interval (i, j)🧩 String DP LeetCode #516 ↗Updated Oct 30, 2026

Problem

Given a string s, return the length of its longest subsequence (delete any characters, keep the order of the rest) that reads the same forwards and backwards.

Input"bbbab"Output4 ("bbbb")

Input"cbbd"Output2 ("bb")

1 ≤ s.length ≤ 1000 · lowercase English letters only

Try it yourself

Java

class Solution {
    public int longestPalindromeSubseq(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Look at the two ends of s[i..j]: if s[i] == s[j] they wrap the best palindrome inside (2 + f(i+1, j-1)); otherwise one end must be dropped (max(f(i+1, j), f(i, j-1))). Only O(n²) intervals exist.

PatternString DP

Instinct Two strings compared char by char (match, edit, interleave) means dp[i][j] over prefixes; one string's palindromes or splits means dp[l][r] or dp[i].

Memory hack Match? Go diagonal. Mismatch? Ask the neighbours. Up drops a char from s, left drops one from t, diagonal uses both.

Open the String DP guide →

Approaches

Brute ForcePlain Recursion on Intervals

Time O(2ⁿ)Space O(n)

f(l, r) = answer for s[l..r]. Empty interval → 0, one char → 1. A mismatch spawns two calls, each only one character shorter, so the call tree doubles per level and recomputes the same intervals.

Java

public int longestPalindromeSubseq(String s) {
    return f(s, 0, s.length() - 1);
}
private int f(String s, int l, int r) {
    if (l > r) return 0;
    if (l == r) return 1;
    if (s.charAt(l) == s.charAt(r)) return 2 + f(s, l + 1, r - 1);
    return Math.max(f(s, l + 1, r), f(s, l, r - 1));
}

Direct translation of the recurrence, but exponential.

BetterMemoized Recursion (Top-Down)

Time O(n²)Space O(n²)

Cache f(l, r) in memo[l][r]. There are n(n+1)/2 intervals and each is solved once in O(1), giving O(n²). 0 works as “not computed” because every non-empty interval has an answer ≥ 1.

Java

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    return f(s, 0, n - 1, new int[n][n]);
}
private int f(String s, int l, int r, int[][] memo) {
    if (l > r) return 0;
    if (l == r) return 1;
    if (memo[l][r] != 0) return memo[l][r];
    if (s.charAt(l) == s.charAt(r)) return memo[l][r] = 2 + f(s, l + 1, r - 1, memo);
    return memo[l][r] = Math.max(f(s, l + 1, r, memo), f(s, l, r - 1, memo));
}

Quadratic, but an n² table plus O(n) recursion depth.

OptimalBottom-Up, One Row

Time O(n²)Space O(n)

Row i of the table (dp[i][·]) needs only row i+1, so loop i from n-1 down and keep one array. Before overwriting, dp[j] is f(i+1, j), dp[j-1] is the new f(i, j-1), and prev holds the old dp[j-1] = f(i+1, j-1).

Java

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[] dp = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = 1;
        int prev = 0; // f(i+1, j-1)
        for (int j = i + 1; j < n; j++) {
            int old = dp[j]; // f(i+1, j)
            dp[j] = s.charAt(i) == s.charAt(j) ? prev + 2 : Math.max(old, dp[j - 1]);
            prev = old;
        }
    }
    return dp[n - 1];
}

Dry run"bbbab"

changed

i=4
0

0

0

0

1

'b' alone = 1
i=3
0

0

0

1

1

'ab' → 1
i=2
0

0

1

1

3

'bab': b=b → 1+2
i=1
0

1

2

2

3

'bbab' → 3
i=0
1

2

3

3

4

'bbbab' → 4 ✔

Same quadratic time with linear memory and no recursion.

Pro tip

Shortcut: LPS(s) = LCS(s, reverse(s)) — reuse the LCS solution if you already have it.

At a glance

Level	Approach	Time	Space
Brute Force	Plain Recursion on Intervals	`O(2ⁿ)`	`O(n)`
Better	Memoized Recursion (Top-Down)	`O(n²)`	`O(n²)`
Optimal	Bottom-Up, One Row	`O(n²)`	`O(n)`

Common pitfalls

Mixing up with Longest Palindromic Substring (5) — here gaps are allowed.
Filling the 2-D table row-by-row from i = 0 — dp[i+1] isn't ready.
Forgetting the base case l == r → 1 (or dp[i] = 1).

Interview tips

Frame it as interval DP: state = (left, right), shrink from the ends.
Mention the LCS-with-reverse reduction as a quick sanity check.
Note the fill order: i descending, j ascending.

Pattern

Interval DP on (i, j) → palindrome/subsequence questions answered by comparing the two ends.

My notes saved in this browser