A palindrome is any string that is exactly the same as its reversal, likeI, or D

Question

A palindrome is any string that is exactly the same as its reversal, likeI, or DEED, or RACECAR, or AMANAPLANACANALPANAMA. For example, in sequence MAHDYNAMICPROGRAMZLETMESHOWYOUTHEM, the longest subsequence that is a palindrome is MHYMRORMYHM, so given that string as input, your algorithm should output the number 11. Describe in pseudo-code an O(n2) time algorithm to find the length of the longest subsequence of a given string that is also a palindrome. The key is to find a recursive description of the optimal solution in terms of the optimal solution of smaller subproblems. If you are unable to find an O(n2) time algorithm, then for part marks, you can give an O(n3) or O(n4) time algorithm. Analyze the running time of your algorithm.

Explanation / Answer

a)

Optimal substrcuture in this problem

Let L is longest palindoromic subsequence and S is input string

Let L is a two D matrix of n * n where n is length of S

Recursive substructure

for i in 1 to n:
L(i, i) = 1

if S[i] != s[j]:
L(i, j) = max{L(i+1, j), L(i, j-1)}

else if length is 2 and both chacrter are same i.e j = i+1
L(i, j) = 2

else

L(i, j) = L(i+1, j-1) + 2

In this solution as we are saving values in L(i, j) we do not need to recompute them and hence this will give optimal result

here is detailed code like pseduo -code

LongestPalindromLength(S)

n = length of S

create a 2d array L for memoizatio of n * n

for i = 0 to n-1

L[i][i] = 1

for k = 2 to n

for i = 0 to n- k + 1

j = i+k-1

if S[i] == S[j] && k == 2 // size is 2

L[i][j] = 2

else if S[i] == S[j]

L[i][j] = L[i+1][j-1] + 2

else

L[i][j] = max(L[i][j-1], L[i+1][j])

return L[0][n-1]

b)

Now as we can see there two nested for loops inner loop is doing O(n) work for each outer loop iteration

so hence Time Complexity = O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.