# Longest palidromic subsequence

Jump to navigation Jump to search

Longest Palindromic Subsequence is the problem of finding the longest palindromic subsequence of a sequence.

The solution utilizes dynamic programming.

## Overview

The problem is usually defined as:

Given a sequence of items, find the length of the longest subsequence which is a palindrome. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, in the string abcdefg, "abc", "abg", "bdf", "aeg" are all subsequences.

## Recursive solution

psuedo code:

```def lps_len(m, n,S):
"""This function returns length of longest palindromic sequence of x and y."""
if n==m:
return 1
if S[m]==S[n] and m+1==n:
return 2
if S[m]==S[n]:
return lps(m+1,n-1,S)+2
else:
return max(lps(m+1,n,S),lps(m,n-1,S)
```

## Dynamic programming

pseudo code:

```def lps(S):
n = len(S)
LPS=[*n]*n
for i in range(n):
LPS[i][i]=1
for i in range(n-1,-1,-1):
for j in range(i+1,n):
if S[i]==S[j]:
LPS[i][j]=2+LPS[i+1][j-1]
else:
LPS[i][j]=max(LPS[i+1][j],LPS[i][j-1])
return LPS[n-1]
```