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 <[email protected]> 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 [email protected]. > -- 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 [email protected].
