Hi Vikas and Prateek, Vikas, the 'd' is arbitrary. The question is simply to return the padded string such that the number of similar characters in the padded smaller string (which is now equal in length to the bigger string) and the bigger string is the minimum.
Prateek, I can understand the solution you mentioned- be great if you can send your code. However, I understand that the smaller string has to be moved (m-n) times and each time there are n comparisons. If anybody has any ideas for additional optimizations (even with lets say additional space complexity), it would be awesome to hear! On Tue, Oct 7, 2014 at 11:29 PM, Prateek Khandelwal <pratv...@gmail.com> wrote: > Just think in this manner that put 0 star in front, then 1 star in front > and so on and while doing this just compare both the strings. If you are > not able to understand just tell me I will mail my code to you. > > Prateek Khandelwal > Software Engineer in Directi > +91-7042393719 > > On Tue, Oct 7, 2014 at 11:23 PM, Prateek Khandelwal <pratv...@gmail.com> > wrote: > >> I think this question can be done in O((m-n)*n) where m is the length of >> larger string and n is the length of smaller string >> >> Prateek Khandelwal >> Software Engineer in Directi >> +91-7042393719 >> >> On Tue, Oct 7, 2014 at 6:06 PM, vikas <vikas.rastogi2...@gmail.com> >> wrote: >> >>> question unclear ?What is to be minimize ? >>> in given example: >>> ca*d*bch >>> abc >>> >>> what is role of "d" ? >>> >>> >>> On Monday, 6 October 2014 22:52:10 UTC+5:30, Rishav wrote: >>>> >>>> Hi everyone, >>>> >>>> I was asked this question recently in an interview: Given two strings >>>> of unequal length, you have to pad the smaller string (either at the >>>> beginning or the end or both, no insertions allowed) with any character you >>>> want. The idea is to minimize the index-wise non-similar elements in both >>>> the strings. >>>> >>>> Example: >>>> abc >>>> cadbch >>>> >>>> The character we want should be: >>>> >>>> **abc*, such that the difference is just one(b and c are same for both >>>> strings in this position). I only found a solution with O(mn) complexity. >>>> Anybody can suggest any optimizations? >>>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to algogeeks+unsubscr...@googlegroups.com. >>> >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
