dynamic-programming Subsequence Related Algorithms Longest Palindromic Subsequence

Example

Given a string what is the longest palindromic subsequence(LPS) of it? Let's take a string agbdba. The LPS of this string is abdba of length 5. Remember, since we're looking for subsequence, the characters need not to be continuous in the original string. The longest palindromic substring of the sequence would be bdb of length 3. But we'll concentrate on the subsequence here. We're going to use dynamic programming to solve this problem.

At first, we'll take a 2D array of the same dimension of our original sequence. For our example: S = "agbdba", we'll take dp[6][6] array. Here, dp[i][j] represents the length of the LPS we can make if we consider the characters from s[i] to s[j]. For example. if our string was aa, dp[0][1] would store 2. Now we'll consider different lengths of our string and find out the longest possible length we can make out of it.

Length = 1:
Here, we are considering only 1 character at a time. So if we had a string of length 1, what is the LPS we can have? Of course the answer is 1. How to store it? dp[i][j] where i is equal to j represents a string of length 1. So we'll set dp[0][0], dp[1][1], dp[2][2], dp[3][3], dp[4][4], dp[5][5] to 1. Our array will look like:

+---+---+---+---+---+---+---+
|   | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 |   |   |   |   |   |
+---+---+---+---+---+---+---+
| 1 |   | 1 |   |   |   |   |
+---+---+---+---+---+---+---+
| 2 |   |   | 1 |   |   |   |
+---+---+---+---+---+---+---+
| 3 |   |   |   | 1 |   |   |
+---+---+---+---+---+---+---+
| 4 |   |   |   |   | 1 |   |
+---+---+---+---+---+---+---+
| 5 |   |   |   |   |   | 1 |
+---+---+---+---+---+---+---+

Length = 2:
This time we'll consider strings of length 2. Now considering strings of length 2, the maximum length of LPS can be 2 if and only if the two characters of the string is same. So our strategy will be:

j := i + Length - 1
if s[i] is equal to s[j]
    dp[i][j] := 2
else
    dp[i][j] := 1

If we fill our array following the strategy for Length = 2, we'll get:

+---+---+---+---+---+---+---+
|   | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 |   |   |   |   |
+---+---+---+---+---+---+---+
| 1 |   | 1 | 1 |   |   |   |
+---+---+---+---+---+---+---+
| 2 |   |   | 1 | 1 |   |   |
+---+---+---+---+---+---+---+
| 3 |   |   |   | 1 | 1 |   |
+---+---+---+---+---+---+---+
| 4 |   |   |   |   | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 |   |   |   |   |   | 1 |
+---+---+---+---+---+---+---+

Length = 3:
Now we're looking at 3 characters at a time for our original string. From now on the LPS we can make from our string will be determined by:

• If the first and last characters match we'll have at least 2 items from which we can make the LPS + if we exclude the first and last character, what ever the best we can make from the remaining string.
• If the first and last characters do not match, the LPS we can make will come from either excluding the first character or the last character, which we've already calculated.

To summerize,

j := i + Length - 1
if s[i] is equal to s[j]
    dp[i][j] := 2 + dp[i+1][j-1]
else
    dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if

If we fill the dp array for Length = 3 to Length = 6, we'll get:

+---+---+---+---+---+---+---+
|   | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 1 | 1 | 3 | 5 |
+---+---+---+---+---+---+---+
| 1 |   | 1 | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 2 |   |   | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 3 |   |   |   | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
| 4 |   |   |   |   | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 |   |   |   |   |   | 1 |
+---+---+---+---+---+---+---+

This is our required dp array and dp[0][5] will contain the length of the LPS. Our procedure will look like:

Procedure LPSLength(S):
n := S.length
dp[n][n]
for i from 0 to n
    dp[i][i] := 1
end for
for i from 0 to (n-2)
    if S[i] := S[i+1]
        dp[i][i+1] := 2
    else
        dp[i][i+1] := 1
    end if
end for
Length := 3
while Length <= n
    for i from 0 to (n - Length)
        j := i + Length - 1
        if S[i] is equal to s[j]
            dp[i][j] := 2 + dp[i+1][j-1]
        else
            dp[i][j] := max(dp[i+1][j], dp[i][j-1])
        end if
    end for
Length := Length + 1
end while
Return dp[0][n-1]

The time complexity of this algorithm is O(n²), where n is the length of our given string. Longest Palindromic Subsequence problem is closely related to Longest Common Subsequence. If we take the second string as the reverse of the first string and calculate the length and print the result, that will be the longest palindromic subsequence of the given string. The complexity of that algorithm is also O(n²).