Given a string S of length n, design an efficient algorithm which computes the l

Question

Given a string S of length n, design an efficient algorithm which computes the longest palindromic subsequence of S (not necessarily consecutive). A palindromic string is one which reads the same front and back. For example, the string RAECEDCAUR has inside it palindromes RR, RAECEAR, RACECAR, etc. At first, you provide a recursive definition of the length of a longest palindromic subsequence of a string. Based on this recursive definition, you provide a dynamic programming algorithm. Your algorithm must run in time O(n2).

Explanation / Answer

First solution:
==============
The Longest Palindrome Subsequence (LPS) of a string is simply the Longest Common Subsequence of itself and its reverse. Since it's simply a LCS variant, it also takes O(n²) time and O(n²) memory.

Second solution:
===============
The second solution is a bit more elaborated, but also follows the general LCS template. It comes from the following recurrence:

lps(s[i..j]) =
s[i] + lps(s[i+1]..[j-1]) + s[j], if s[i] == s[j];
max(lps(s[i+1..j]), lps(s[i..j-1])) otherwise
The pseudocode for calculating the length of the lps is the following:

compute-lps(s, n):

// palindromes with length 1
for i = 1 to n:
c[i, i] = 1
// palindromes with length up to 2
for i = 1 to n-1:
c[i, i+1] = (s[i] == s[i+1]) ? 2 : 1

// palindromes with length up to j+1
for j = 2 to n-1:
for i = 1 to n-i:
if s[i] == s[i+j]:
c[i, i+j] = 2 + c[i+1, i+j-1]
else:
c[i, i+j] = max( c[i+1, i+j] , c[i, i+j-1] )
  
It still takes O(n²) time and memory if I want to effectively construct the lps (because I 'll need all cells on the table). Analysing related problems, such as LIS, which can be solved with approaches other than LCS-like with less memory (LIS is solvable with O(n) memory), I was wondering if it's possible to solve it with O(n) memory, too.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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