Searching a minimal string meeting some conditions

Question

Recently, I was asked the following problem during an interview.

Given a string S, I need to find another string S2 such that S2 is a subsequence of S and also S is a subsequence of S2+reverse(S2). Here '+' means concatenation. I need to output the min possible length of S2 for given S.

I was told that this is a dynamic programming problem however I was unable to solve it. Can somebody help me with this problem?

EDIT-

Is there a way to do this in O(N²) or less.

Answer 1

There are 2 important aspects in this problem.

1. Since we need S as a substring of S2+reverse(S2), S2 should have atleast n/2 length.
2. After concatenation of S2 and reverse(S2), there is a pattern where the alphabets repeats such as

So the solution is to check from the center of S to end of S for any consecutive elements. If you find one then check the elements on either side as shown.

Now if you are able to reach till the end of the string, then the minimum number of elements (result) is the distance from start to the point where you find consecutive elements. In this example its C i.e 3.

We know that this may not happen always. i.e you may not be able to find consecutive elements at the center. Let us say the consecutive elements are after the center then we can do the same test.

Main string

Substring

Concatenated string

Now arrives the major doubt. Why we consider only the left side starting from center? The answer is simple, the concatenated string is made by S+reverse(S). So we are sure that the last element in the substring comes consecutive in the concatenated string. There is no way that any repetition in the first half of the main string can give a better result because at least we should have the n alphabets in the final concatenated string

Now the matter of complexity: Searching for consecutive alphabets give a maximum of O(n) Now checking elements on either side iteratively can give a worst case complexity of O(n). i.e maximum n/2 comparisons. We may fail many times doing the second check so the we have a multiplicative relation between the complexities i.e O(n*n).

I believe this is a correct solution and didn't find any loophole yet.