swordx's blog

By swordx, history, 4 months ago, , Hello Guys,

Can you share your thoughts on the following question:

Given a string, we have to find the longest non-overlapping repeating subsequence. For example, If we have a string like "abdead", then here the answer is "ad" because longest repeating subsequence is "ad" which is non-overlapping.

My initial thought on this question is that we can use the concept of longest common subsequence but we need to manage the non-overlapping part. Comments (10)
 » Split the string into two strings $s_1,s_2$ such that $s=s_1s_2$ in all possible ways (there are $n-1$ ways) and then find the LCS of those two strings. The largest such LCS is the solution. The complexity is $O(n^3)$. It can probably be done faster though.
•  » » You can use ternary search for the split, and it'll be $O(n^2log(n))$
•  » » » You cannot use ternary search. For example for s = "sxyaatxysaaxyt" the LCSs for subsequent splits are 1 2 3 3 4 5 4 5 4 3 3 2 1.However, there is $O(n^2)$ algorithm for finding the optimal split.
•  » » » No, you need to find the longest subsequence which has the form $ss$ for some string $s$, not two identical non-overlapping subsequences.