15-2 Longest palindrome subsequence

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length $1$, $\text{civic}$, $\text{racecar}$, and $\text{aibohphobia}$ (fear of palindromes).

Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input $\text{character}$, your algorithm should return $\text{carac}$. What is the running time of your algorithm?

Let $A[1..n]$ denote the array which contains the given word. Taking inspiration from the Longest-Common-Subsequence problem earlier in the chapter, we can consider each pair of indexes $i$ and $j$ such that $0 \le i < j < n$ as a decision point where each character-pair may be either included or excluded from the longest-palindromic substring.

Our recursion is defined as:

• If $A[i] = A[j]$, then characters $i$ and $j$ must be in the longest palindromic substring (else we contradict that our recursion solves for the longest possible substring)
• If $A[i] \ne A[j]$, then the longest palindromic substring is found in one of $A[i + 1..j]$ or $A[i..j + 1]$, forming our recursive subproblems

Our recursive base case is the single-character palindrome, i.e. the case where $i = j$. From there we build our subproblems up taking one character-length step at a time until we reach $n$ our size of the initial array.

LPS-LENGTH(A, n)
    initialize a table LPS of size n by n
    initialize a table DECISIONS of size n by n

    for i = 1 to n
        // Base case, a palindrome of length 1
        LPS[i][i] = 1
        DECISIONS[i][i] = "TAKE ONE"

    for length = 1 to n
        for i = 0 to (n - length)
            j = i + length
            if A[i] == A[j]
                LPS[i][j] = 2 + LPS[i + 1][j - 1]
                DECISIONS[i][j] = "TAKE BOTH"
            else if LPS[i + 1][j] > LPS[i][j - 1]
                LPS[i][j] = LPS[i + 1][j]
                DECISIONS[i][j] = "IGNORE LEFT"
            else
                LPS[i][j] = LPS[i][j - 1]
                DECISIONS[i][j] = "IGNORE RIGHT"

    return LPS, DECISIONS

As is easily intuited by the above algorithm, our algorithm $O(n^2)$, needing to iterate over $n$ subproblem-lengths and having to compare $O(n)$ index pairs for each.

And then similarly to the Longest-Common-Subsequence problem again, we can traverse the $\text{DECISIONS}$ matrix to reconstruct our palindrome:

PRINT-LPS(A, DECISIONS, i, j)
    if DECISIONS[i][j] == "TAKE ONE":
        print A[i]
    else if DECISIONS[i][j] == "TAKE BOTH":
        print A[i]
        PRINT-LCS(A, DECISIONS, i + 1, j - 1)
        print A[j]
    else if DECISIONS[i][j] == "IGNORE LEFT":
        PRINT-LCS(A, DECISIONS, i + 1, j)
    else
        // IGNORE_RIGHT
        PRINT-LCS(A, DECISIONS, i, j - 1)