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: With an input string, MAXDYAM, the LPS is MADAM, which has length = 5 With an input string, BxAoNxAoNxA, the LPS is ANANA, which has length = 5 With an input string, BANANO, the LPS is NAN, which has length = 3 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

        Contact Us

programmersdoor@gmail.com

  • LinkedIn
  • Facebook
  • Instagram

©2023 by Programmers Door