Given two substrings A (N characters, all distinct) and B (M characters, not necesarilly distinct). Insert characters in B, at anyposition, so that A becomes a substring of B.

Best, I could do was in O(N*M), using 2D dynamic programming, which passed half the cases. Any better way?

In the assessment, they had not mentioned the array A was sorted. It it were, a O(Mlog(M)) type solution is possible, using Largest increasing subsequence. The LIS based solution (considering that the array A is sorted) passes all cases. I think that they simply forgot to mention that the array A is sorted :-(. Is it so, or am I wrong?