2
$\begingroup$

Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A.

Example: A = cabca

the sub-sequence S = abc is the longest of such sub-sequences.

reading S forward (abc): cabca

reading S reverse (cba): cabca

How to compute the length of such an S ?

$\endgroup$

1 Answer 1

2
$\begingroup$

One option is to reduce your problem to Longest Common Subsequence. I'll let you figure out how.

$\endgroup$
6
  • $\begingroup$ Thanks for this. Could you give a bigger hint please ? $\endgroup$
    – rranjik
    Commented Oct 29, 2018 at 0:50
  • $\begingroup$ Unfortunately it would be difficult for me to give further hints without giving away the solution. $\endgroup$ Commented Oct 29, 2018 at 0:57
  • $\begingroup$ I call it longest 2 sided sub-sequence, the following is my recurrence. | 0 if i>j l2sss(i,j) = | 1 if i = j | 2 + l2sss(i+1, j-1) if s[i]==s[j] //include both | max (2 + l2sss(i+1, find_last_of(s[i])-1), l2sss(i+1, j) two cases within max 1> include s[i], so the problem size become i+1 (because s[i] was included) to find_last_of(s[i]-1) and 2> I exclude s[i]. This does not seem to work (when I implemented this, it does not evaluate to the right answer) and seems to force the string S to be a palindrome (it wasn't a requirement). $\endgroup$
    – rranjik
    Commented Oct 29, 2018 at 2:07
  • $\begingroup$ Sorry, I tried to pretty print that recurrence equation, it did not work out as I expected. $\endgroup$
    – rranjik
    Commented Oct 29, 2018 at 2:20
  • $\begingroup$ Could you please tell me what is wrong with my recurrence ? $\endgroup$
    – rranjik
    Commented Oct 29, 2018 at 2:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.