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²)`

.