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[0][n-1]

def test_function(test_case):
    string = test_case[0]
    solution = test_case[1]
    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!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor

---

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

Follow Programmers Door for more.

#blog #interview #placement