Message

You are given 2 strings :- S and t.

You have to convert any sub-string of S to t with 3 operations

1.  Delete char from sub-string of S (from the endpoints only).
2.  Add char to sub-string of S (at endpoints only)
3.  Change any char of S.

There are few ideas that help you solve this problem:-

=== First of all there always exist an answer. Using |t| operation we can always have string t.

So the first question is do we have to consider those sub-strings of s that are greater than |t| in length? Well you might think you have to but let's analyze the situation a bit:-

=== (a) No matter what we do we have to end in string t. But this sub-string of S [we call it SS from now on] has length > |t| That means we have to delete few characters. |---> Characters can only be deleted from both the end points. So we have to delete few from end points. Now the thing is those that we are going to delete, is there any meaning for considering in the first place? For example: Then we could have just considered the stripped string and then we have saved few delete operations. So we will never need a delete operation.

=== What is the case for addition?

There are two possibilities:-

1. We have sub-string SS. Then we add at beginning some character which was actually at the beginning of sub-string SS in the original string S. It's similar to the previous case will not be necessary as we can avoid this operation by adding to the sub-string originally.

2. We have added a completely different character. Now that does not match that of original string. so it will be added. But if we think carefully...isn't it an change operation?

S = ABBCBA

t = BBCD

Now in case of sub-string "BB" we will add 'C' but it is already in the string immediate next to the end of the string..so why don't we consider sub-string "BBC"

Now when considering "BBC" we will try to add 'D' and there is no match with the immediate next of that 'C' in string S. So we will add it. But this add is equivalent to a change if we consider sub-string "BBCB".

And also we don't need to consider any string < |t|. So we have to check all |t| length sub-strings.

Now it indicates we use |t| length sub-strings and then compare with the target t. Is this ok? Ah we have missed a small case.

for example:- S = ABCD T = XA How we will check?

   [AB]CD   A[BC]D   AB[CD]
    XA        XA        XA  ANS = 2 --->WRONG
   But we can do it in 1.
    [A]BCD  --> prepned X..[XA]. 

So why does this happen? We have to check whether A matches with or not with every position in the array. We were not doing it earlier. How to do that?

  ##ABCD##
  XA
  ##ABCD##
   XA
  ##ABCD##
    XA
  ##ABCD##
     XA
  ##ABCD##
      XA
  ##ABCD##
       XA

Well this way we checked every character against every character. So by this we are sure that we won't miss anything.

This is what I got from the problem..anybody is suggested to clarify or modify this idea to have a better explanation. Thanks.

EDIT: 1. I dont care about upvote but I wrote this so that I can verify my understanding and also to provide with a English version of the editorial on my own words. Whatever it is just point out if there is any error on what I said? Thanks. ****