Longest Palindromic Subsequence: Interval DP Explained

A new kind of state: the interval

In bbbab the subsequence bbbb is a palindrome of length 4. A palindrome is defined by its two ends matching, so the natural subproblem is a stretch of the string: L(i, j), the longest palindromic subsequence inside s[i..j].

Recurrence

L(i, j)

if s[i] = s[j]: 2 + L(i + 1, j − 1) (both ends belong to it);
otherwise max(L(i + 1, j), L(i, j − 1)) (drop one end).

base cases

L(i, i) = 1; an empty interval (i > j) is 0.

An interval reads strictly shorter intervals, so the table is filled by length: all intervals of length 1, then 2, and so on. The answer is L(0, n − 1).

Bottom-up, by length

L(i, j) for bbbab, filled diagonal by diagonal (each diagonal is one length).

Step 1 / 16

Base cases filled first.
Step 2 / 16

[0, 0] is a single character: 1.
Step 3 / 16

[1, 1] is a single character: 1.
Step 4 / 16

[2, 2] is a single character: 1.
Step 5 / 16

[3, 3] is a single character: 1.
Step 6 / 16

[4, 4] is a single character: 1.
Step 7 / 16

s[0] = s[1] = 'b': 2 + inside = 2.
Step 8 / 16

s[1] = s[2] = 'b': 2 + inside = 2.
Step 9 / 16

'b' ≠ 'a': drop an end, 1.
Step 10 / 16

'a' ≠ 'b': drop an end, 1.
Step 11 / 16

s[0] = s[2] = 'b': 2 + inside = 3.
Step 12 / 16

'b' ≠ 'a': drop an end, 2.
Step 13 / 16

s[2] = s[4] = 'b': 2 + inside = 3.
Step 14 / 16

'b' ≠ 'a': drop an end, 3.
Step 15 / 16

s[1] = s[4] = 'b': 2 + inside = 3.
Step 16 / 16

s[0] = s[4] = 'b': 2 + inside = 4. L(0, 4) = 4: bbbb.

Implementation

In six languages:

def longest_pal_subseq(s):
    n = len(s)
    nxt = [0] * n                        # row i + 1 of the table
    for i in range(n - 1, -1, -1):
        cur = [0] * n
        cur[i] = 1                       # a single character
        for j in range(i + 1, n):
            if s[i] == s[j]:
                cur[j] = 2 + (nxt[j - 1] if i + 1 <= j - 1 else 0)
            else:
                cur[j] = max(nxt[j], cur[j - 1])
        nxt = cur
    return nxt[n - 1]

#include <algorithm>
#include <string>
#include <vector>

int solve(std::string s) {
    const int n = s.size();
    std::vector<int> nxt(n, 0), cur(n, 0);          // rows i + 1 and i
    for (int i = n - 1; i >= 0; --i) {
        std::fill(cur.begin(), cur.end(), 0);
        cur[i] = 1;
        for (int j = i + 1; j < n; ++j)
            cur[j] = s[i] == s[j] ? 2 + (i + 1 <= j - 1 ? nxt[j - 1] : 0) : std::max(nxt[j], cur[j - 1]);
        std::swap(nxt, cur);
    }
    return nxt[n - 1];
}

class Solution {
    public int longestPalSubseq(String s) {
        int n = s.length();
        int[] nxt = new int[n], cur = new int[n];        // rows i + 1 and i
        for (int i = n - 1; i >= 0; i--) {
            java.util.Arrays.fill(cur, 0);
            cur[i] = 1;
            for (int j = i + 1; j < n; j++)
                cur[j] = s.charAt(i) == s.charAt(j) ? 2 + (i + 1 <= j - 1 ? nxt[j - 1] : 0) : Math.max(nxt[j], cur[j - 1]);
            int[] t = nxt; nxt = cur; cur = t;
        }
        return nxt[n - 1];
    }
}

function longestPalSubseq(s) {
  const n = s.length;
  let nxt = new Array(n).fill(0);          // row i + 1
  for (let i = n - 1; i >= 0; i--) {
    const cur = new Array(n).fill(0);
    cur[i] = 1;
    for (let j = i + 1; j < n; j++)
      cur[j] = s[i] === s[j] ? 2 + (i + 1 <= j - 1 ? nxt[j - 1] : 0) : Math.max(nxt[j], cur[j - 1]);
    nxt = cur;
  }
  return nxt[n - 1];
}

fn solve(s: &str) -> i64 {
    let c: Vec<u8> = s.bytes().collect();
    let n = c.len();
    let mut nxt = vec![0i64; n];                        // row i + 1
    for i in (0..n).rev() {
        let mut cur = vec![0i64; n];
        cur[i] = 1;
        for j in i + 1..n {
            cur[j] = if c[i] == c[j] {
                2 + if i + 1 <= j - 1 { nxt[j - 1] } else { 0 }
            } else {
                nxt[j].max(cur[j - 1])
            };
        }
        nxt = cur;
    }
    nxt[n - 1]
}

import Data.Array

solve :: String -> Int
solve s = table ! (0, n - 1)
  where
    n = length s
    a = listArray (0, n - 1) s
    -- a lazy table: each interval refers only to shorter ones
    table = array ((0, 0), (n - 1, n - 1)) [((i, j), go i j) | i <- [0 .. n - 1], j <- [0 .. n - 1]] :: Array (Int, Int) Int
    go i j
      | i > j = 0
      | i == j = 1
      | a ! i == a ! j = 2 + (if i + 1 <= j - 1 then table ! (i + 1, j - 1) else 0)
      | otherwise = max (table ! (i + 1, j)) (table ! (i, j - 1))

The same code is the reference solution to Longest palindromic subsequence, where it is compiled and run against the tests in all six languages.

TimeO(n²)

SpaceO(n²), or O(n) keeping two diagonals

A shortcut worth knowing: the longest palindromic subsequence of s equals the longest common subsequence of s and its reverse.