Question

4.A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, civic, racecar, abba,…

Give a DP algorithm to find the longest palindrome that is a subsequence of a given input string. What is the running time of your algorithm? (40 points).

•Examples:

•Given the input “character”, your algorithm should return “carac”.

•Given the input “TTATGTGAT”, your algorithm should return “TATGTAT”

Python Code only

Answer 1

To obtain a Dp algorithm lets first derive a recursive solution
we take 2 pointers one at the begining and one for the end, as we know
that for pallindrome, given a String s
if start = 0, end = len(s)-1
while start < end
then s[start]==s[end]
start--, end--

Case 1:
   char at start == char at end
   then we take both the characters as possible candidate for result and we
   proceed to get the ans for string of length start+1 -> end-1
Case 2:
   char at start != char at end
   then the largest palindrominc subsequence may be present at (start -> end-1) or (start+1 -> end)

example :
str = S A C A B S
start = 0, end = 6
as str[start] == str[end] now we check for start+1 -> end-1

start = 1 end = 5
A != B
so first decrement end and check string A C A
then increment start and check string C A B

RECURSIVE CODE:

def recursive(start,end,seq):
   if (start>end): return ""
   if(start == end): return seq[start]
   #case 1
   if(seq[start] == seq[end]):
       return seq[start] + recursive(start+1,end-1,seq) + seq[end]
   #case 2
   else:
       s1 = recursive(start+1,end,seq)
       s2 = recursive(start,end-1,seq)

       if(len(s1)>len(s2)):return s1
       else: return s2

as you can see in this recusrive approach there are many overlapping sub problem
so we correct that using memoization (DP) also called Top Down approach.
we do so by storing intermediate results in a dictionary as a hash so that we dont have to recompute
the already calculated values
we do so by making a dictionary which stores "start end" and corresponding string

DP CODE:

def memoization(start,end,seq,dp):
   if (start>end): return ""
   if(start == end): return seq[start]
   #check in memory
   if(dp.get(f"{start} {end}")):
       return dp[f"{start} {end}"]
   #case 1
   if(seq[start] == seq[end]):
       #store in memory
       dp[f"{start} {end}"] = seq[start] + memoization(start+1,end-1,seq,dp) + seq[end]
       return dp[f"{start} {end}"]
   #case 2
   else:
       s1 = memoization(start+1,end,seq,dp)
       s2 = memoization(start,end-1,seq,dp)
       #store in memory
       if(len(s1)>len(s2)):
           dp[f"{start} {end}"]=s1
           return s1
       else:
           dp[f"{start} {end}"]=s2
           return s2  

s = "character"
print(recursive(0,len(s)-1,s))

dp={}
print(memoization(0,len(s)-1,s,dp))