Search

# Longest Palindromic Subsequence

In general, a palindrome is a string that reads the same backwards as forwards, e.g., MADAM. In the last notebook, we saw that in a given string, a subsequence is an ordered set of characters that need not necessarily be a contiguous substring, e.g., ABC is a subsequence in AXBYC with length = 3.

The Longest Palindromic Subsequence (LPS) is the most lengthy sequence of characters that is a palindrome. In this notebook, you'll be tasked with finding the length of the LPS in a given string of characters.

Examples:

1. With an input string, MAXDYAM, the LPS is MADAM, which has length = 5

2. With an input string, BxAoNxAoNxA, the LPS is ANANA, which has length = 5

3. With an input string, BANANO, the LPS is NAN, which has length = 3

4. With an input string, ABBDBCACB, the LPS is BCACB, which has length = 5

### Example Matrices

Example LPS Subproblem matrix 1:

```input_string = 'BANANO'

LPS subproblem matrix:

B  A  N  A  N  O
B  [[1, 1, 1, 3, 3, 3],
A   [0, 1, 1, 3, 3, 3],
N   [0, 0, 1, 1, 3, 3],
A   [0, 0, 0, 1, 1, 1],
N   [0, 0, 0, 0, 1, 1],
O   [0, 0, 0, 0, 0, 1]]

LPS length:  3```

Example LPS Subproblem matrix 2:

```input_string = 'TACOCAT'

LPS subproblem matrix:

T  A  C  O  C  A  T
T  [[1, 1, 1, 1, 3, 5, 7],
A   [0, 1, 1, 1, 3, 5, 5],
C   [0, 0, 1, 1, 3, 3, 3],
O   [0, 0, 0, 1, 1, 1, 1],
C   [0, 0, 0, 0, 1, 1, 1],
A   [0, 0, 0, 0, 0, 1, 1],
T   [0, 0, 0, 0, 0, 0, 1]]

LPS length:  7```

Program:

```def lps(input_string):
n = len(input_string)
L = [[0 for x in range(n)] for x in range(n)]
for i in range(n):
L[i][i] = 1

for s_size in range(2,n+1):
for start_idx in range(n-s_size + 1):
end_idx = start_idx + s_size - 1
if s_size == 2 and input_string[start_idx] == input_string[end_idx]:
L[start_idx][end_idx] = 2
elif input_string[start_idx] == input_string[end_idx]:
# general match case
L[start_idx][end_idx] = L[start_idx+1][end_idx-1] + 2
else:
# no match case, taking the max of two values
L[start_idx][end_idx] = max(L[start_idx][end_idx-1], L[start_idx+1][end_idx])
return L[n-1]

def test_function(test_case):
string = test_case
solution = test_case
output = lps(string)
print(output)
if output == solution:
print("Pass")
else:
print("Fail")

string = 'BxAoNxAoNxA'
solution = 5
test_case = [string, solution]
test_function(test_case)

string = 'BANANO'
solution = 3
test_case = [string, solution]
test_function(test_case)

string = "TACOCAT"
solution = 7
test_case = [string, solution]
test_function(test_case)```

Happy Coding!

Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem

19 views

See All