☕ DSA Java Articles

Topics › Dynamic Programming › DP on Strings

Longest palindromic subsequence

Hard TUF ID 310 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a string s, return the length of its longest palindromic subsequence: the longest sequence of characters, taken from s in order but not necessarily adjacent, that reads the same forwards and backwards.

Constraints (LeetCode 516): 1 ≤ n ≤ 1000, lowercase English letters. The Java methods also accept the empty string.

Example 1

s = "bbbab"
answer = 4          // "bbbb": skip the 'a'

Example 2

s = "cbbd"
answer = 2          // "bb"

The recurrence on a range

Let f(i, j) be the answer for the range s[i..j] (both ends included). Compare the two ends:

Base cases: an empty range (i > j) gives 0, a single character (i == j) gives 1.

Approach 1: Recursion

Intuition. Implement the recurrence directly, starting from the full range (0, n - 1).

Algorithm.

  1. If i > j return 0; if i == j return 1.
  2. If the ends match, return 2 + f(i + 1, j - 1).
  3. Otherwise return max(f(i + 1, j), f(i, j - 1)).
static int recursive(String s) {
    return solve(0, s.length() - 1, s);
}

/** Longest palindromic subsequence inside s[i..j] (inclusive). */
static int solve(int i, int j, String s) {
    if (i > j) return 0;                                     // empty range
    if (i == j) return 1;                                    // a single character is a palindrome
    if (s.charAt(i) == s.charAt(j)) return 2 + solve(i + 1, j - 1, s);   // use both ends as the outer pair
    return Math.max(solve(i + 1, j, s), solve(i, j - 1, s)); // at least one end is unused: drop it
}

Complexity. Time O(2^n): on a string with no repeated letters every call branches twice and each branch shrinks the range by one. Space O(n) for the stack.

Approach 2: Memoization

Intuition. A range is identified by (i, j), so there are only about n^2 / 2 of them, but both branches of a mismatch reach the range (i + 1, j - 1) again. Cache every answer; -1 marks “not computed”.

Algorithm.

  1. dp[n][n] filled with -1.
  2. Same recursion, returning cached values and storing new ones.
static int memoization(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(0, n - 1, s, dp);
}

static int memo(int i, int j, String s, int[][] dp) {
    if (i > j) return 0;
    if (i == j) return 1;
    if (dp[i][j] != -1) return dp[i][j];
    if (s.charAt(i) == s.charAt(j)) return dp[i][j] = 2 + memo(i + 1, j - 1, s, dp);
    return dp[i][j] = Math.max(memo(i + 1, j, s, dp), memo(i, j - 1, s, dp));
}

Complexity. Time O(n^2), space O(n^2) plus O(n) stack.

Approach 3: Tabulation

Intuition. f(i, j) reads f(i + 1, ·) (a shorter range starting later) and f(i, j - 1) (a shorter range in the same row). So fill rows with i going down from n - 1 to 0, and within a row let j go up from i + 1. Cells below the diagonal (i > j) are empty ranges and stay 0, which is exactly what dp[i + 1][j - 1] must return when j == i + 1.

Algorithm.

  1. For i = n - 1 .. 0: set dp[i][i] = 1; for j = i + 1 .. n - 1 apply the recurrence.
  2. Return dp[0][n - 1].
static int tabulation(String s) {
    int n = s.length();
    if (n == 0) return 0;
    int[][] dp = new int[n][n];                              // entries with i > j stay 0 (empty range)
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) dp[i][j] = 2 + dp[i + 1][j - 1];
            else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
}

Dry run on s = "bbbab" (row i, column j, rows filled bottom to top):

i \ j 0 b 1 b 2 b 3 a 4 b
0 b 1 2 3 3 4
1 b   1 2 2 3
2 b     1 1 3
3 a       1 1
4 b         1

For example dp[2][4]: b == b, so 2 + dp[3][3] = 3 (“bab”). dp[0][4]: b == b, so 2 + dp[1][3] = 2 + 2 = 4 (“bbbb”).

Complexity. Time O(n^2), space O(n^2).

Approach 4: Space optimized

Intuition. Row i reads only row i + 1 and itself. Keep next (row i + 1) and cur (row i), swapping after each row. The one subtle read is next[j - 1] when j == i + 1: that cell is the empty range (i + 1, i), which must be 0. With two recycled arrays it happens to be 0 anyway, but the code says so explicitly rather than relying on which stale values the array holds.

Algorithm.

  1. For i = n - 1 .. 0: cur[i] = 1; for j > i compute from next and cur; swap.
  2. Return next[n - 1] (after the final swap, next is row 0).
static int spaceOptimized(String s) {
    int n = s.length();
    if (n == 0) return 0;
    int[] next = new int[n], cur = new int[n];               // next = row i + 1, cur = row i
    for (int i = n - 1; i >= 0; i--) {
        cur[i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) cur[j] = 2 + (j - 1 > i ? next[j - 1] : 0);  // j == i + 1: nothing inside
            else cur[j] = Math.max(next[j], cur[j - 1]);
        }
        int[] tmp = next; next = cur; cur = tmp;
    }
    return next[n - 1];
}

Complexity. Time O(n^2), space O(n).

Approach 5: Reduce to LCS

Intuition. This is the route the A2Z sheet takes: the answer equals the Longest common subsequence of s and reverse(s).

So the two lengths are equal, and the two-row LCS code answers the problem.

static int viaLcs(String s) {
    String r = new StringBuilder(s).reverse().toString();
    int n = s.length();
    int[] prev = new int[n + 1], cur = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i - 1) == r.charAt(j - 1)) cur[j] = 1 + prev[j - 1];
            else cur[j] = Math.max(prev[j], cur[j - 1]);
        }
        int[] tmp = prev; prev = cur; cur = tmp;
    }
    return prev[n];
}

Complexity. Time O(n^2), space O(n). It does about twice the work of Approach 4, because it fills a full n × n table instead of the upper triangle, but it reuses code you already trust.

Edge cases and pitfalls