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$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for this. Could you give a bigger hint please ? $\endgroup$ – rranjik Oct 29 '18 at 0:50
  • $\begingroup$ Unfortunately it would be difficult for me to give further hints without giving away the solution. $\endgroup$ – Yuval Filmus Oct 29 '18 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 Oct 29 '18 at 2:07
  • $\begingroup$ Sorry, I tried to pretty print that recurrence equation, it did not work out as I expected. $\endgroup$ – rranjik Oct 29 '18 at 2:20
  • $\begingroup$ Could you please tell me what is wrong with my recurrence ? $\endgroup$ – rranjik Oct 29 '18 at 2:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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