6.7

Longest Palindromic Subsequence

Pattern · interval / window (i, j) 2-D table on one string O(n²) 6difficulty
Question — exam style

A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, in the sequence A, C, G, T, G, T, C, A, A, A, A, T, C, G, the subsequences A, C, G, C, A and A, A, A, A are palindromic, while A, C, T is not. Devise an algorithm that takes a sequence x[1…n] and returns the length of the longest palindromic subsequence.

Input:A sequence x[1..n].
Output:The length of the longest palindromic subsequence. (Running time O(n²).)

Model answer

4-part format
aSubproblem in words
T(i, j) = the length of the longest palindromic subsequence within the window x[i..j], for 1 ≤ i ≤ j ≤ n.

This is a window problem: the table is indexed by both endpoints of a sub-range, and entries depend on strictly smaller windows. That's the tell for a 2-D interval table.

bRecurrence math only, with base cases + bounds
T(i, i) = 1 for 1 ≤ i ≤ n T(i, i-1) = 0 for 2 ≤ i ≤ n (empty window) If x[i] = x[j]: T(i, j) = 2 + T(i+1, j-1) Else: T(i, j) = max{ T(i+1, j), T(i, j-1) } for 1 ≤ i < j ≤ n

If the two ends match, they wrap a palindrome of the inside plus 2. If not, drop one end or the other and take the better. The T(i,i-1)=0 base case is what keeps the even-length case well-defined.

cImplementation analysis
(1) # of subproblems
O(n²)
(2) Time to fill table
O(n²) — O(1) per entry
(3) Where answer is extracted
T(1, n)
(4) Time to extract
O(1)
Fill order matters

Entries depend on shorter windows, so fill by increasing window length ℓ = j − i (or decreasing i with increasing j). If asked for pseudocode, an outer loop over length and inner over start index is the clean way to guarantee dependencies are ready.

Optional pseudocode not required by Ed #9

A mechanical translation. Note the outer loop is over window length — that's what guarantees smaller windows are filled first.

function LongestPalinSubseq(x[1..n]):
    for i = 1 to n: T[i][i] = 1
    for i = 2 to n: T[i][i-1] = 0        # empty windows
    for L = 1 to n-1:                    # window length
        for i = 1 to n-L:
            j = i + L
            if x[i] == x[j]:
                T[i][j] = 2 + T[i+1][j-1]
            else:
                T[i][j] = max(T[i+1][j], T[i][j-1])
    return T[1][n]
✎

Try it yourself

worked example + self-test

Match ends → 2+T(i+1,j−1); else max{T(i+1,j), T(i,j−1)}. Fill by window length.

Worked upper-triangle grid

x = A G C T G A (n = 6)

j=1(A) j=2(G) j=3(C) j=4(T) j=5(G) j=6(A) i=1(A) 1 1 1 1 3 5 i=2(G) . 1 1 1 3 3 i=3(C) . . 1 1 1 1 i=4(T) . . . 1 1 1 i=5(G) . . . . 1 1 i=6(A) . . . . . 1 T(1,6): x[1]=x[6]=A → 2+T(2,5)=2+3 = 5
Answer: T(1,6) = 5. One LPS: A G T G A.
Self-test fill by window length, then reveal

x = B B A B C B C A B (n = 9)

Reveal answer
LPS length = 7, e.g. B A C B C A B (also B B C B C B B).